An Asymptotic Version of the Multigraph 1-Factorization Conjecture

2010/10/25 by E. R. Vaughan, Vaughan, E. R. · 1 citation
Mathematics · #05C70 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C70

paper · pdf · doi:10.48550/arxiv.1010.5192

13 pages, 2 figures

arxiv created 2010/10/25 · arxiv updated 2010/10/26

Abstract

We give a self-contained proof that for all positive integers r and all ε> 0, there is an integer N = N(r, ε) such that for all n ≥ N any regular multigraph of order 2n with multiplicity at most r and degree at least (1+ε)rn is 1-factorizable. This generalizes results of Perković and Reed, and Plantholt and Tipnis.

Cited by

• Chromatic index of dense quasirandom graphs

Related

• Number of 1-factorizations of regular high-degree graphs
• Indecomposable 1-factorizations of the complete multigraph λK_2n for every λ≤ 2n
• A note on Hamilton decompositions of even-regular multigraphs
• 1-Factorizations of Pseudorandom Graphs
• 1-factorizations of pseudorandom graphs