
arXiv: 1803.10361
handle: 1721.1/140943
A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E(G). In this paper, we prove that for any ϵ>0, an (n,d,λ)‐graph G admits a 1‐factorization provided that n is even, C0 ≤ d ≤ n−1 (where C0=C0(ϵ) is a constant depending only on ϵ), and λ ≤ d1−ϵ. In particular, since (as is well known) a typical random d‐regular graph Gn,d is such a graph, we obtain the existence of a 1‐factorization in a typical Gn,d for all C0 ≤ d ≤ n−1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Random graphs (graph-theoretic aspects), 1-factorizations, pseudorandom graphs, Coloring of graphs and hypergraphs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), chromatic index, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), edge coloring, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Random graphs (graph-theoretic aspects), 1-factorizations, pseudorandom graphs, Coloring of graphs and hypergraphs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), chromatic index, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), edge coloring, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
