An Asymptotic Version of the Multigraph 1-Factorization Conjecture

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 \ge 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.

No reviews yet.

No comments yet.