1-factorization conjecture

Bondy–Murty, Graph Theory, Appendix A, item 57 · Edge colouring

Bondy–Murty Conjecture — first stated 1989

Attributed to: A.J.W. Hilton

Status partial high confidence

The 1-factorization conjecture has been proved for all sufficiently large n by Csaba, Kühn, Lo, Osthus, and Treglown in a landmark paper published in Memoirs of the American Mathematical Society 244 (2016). Their result establishes that every simple d-regular graph on n even vertices with d ≥ n/2 is d-edge-colourable, provided n exceeds an unspecified absolute constant. The conjecture in full generality—covering all even n with no lower bound on n—remains open.

Cited literature (2)

partial Proof of the 1-factorization and Hamilton decomposition conjectures (2016)

Csaba, B., Kühn, D., Lo, A., Osthus, D., Treglown, A. · Memoirs of the American Mathematical Society 244 (2016), no. 1154 · doi:10.1090/memo/1154

Proves the conjecture (every simple d-regular graph on n even vertices with d ≥ n/2 is d-edge-colourable) for all sufficiently large n; the full statement for all n remains open.
partial Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case (2014)

Kühn, D., Lo, A., Osthus, D. · arXiv preprint · arXiv:1401.4183

Part IV of the four-paper series culminating in the Memoirs proof; handles the case when the graph is close to the union of two disjoint cliques, contributing to the proof for sufficiently large n.

Reviewer notes. The book states both the threshold d ≥ n/2 (Hilton 1989) and the sharper d ≥ 2⌈n/4⌉−1 (Chetwynd–Hilton 1985); the Csaba–Kühn–Lo–Osthus–Treglown Memoirs paper is understood to prove the d ≥ n/2 version for sufficiently large n. The Wikipedia article on '1-factorization conjecture' (verified) explicitly confirms that 'the conjecture was confirmed by Csaba, Kühn, Lo, Osthus and Treglown for sufficiently large n' and that the full general statement remains open. The related OPG record 'goldbergs_conjecture' concerns the overfull graph parameter and chromatic index; Wikipedia notes that the overfull conjecture implies the 1-factorization conjecture, so these are related but distinct problems. Web search was unavailable during this review; status was established via verified WebFetch of the Wikipedia article and arXiv:1401.4183 (Part IV of the proof series). The AMS Memoirs page (memo/1154) returned HTTP 403; the DOI is included from the editorial note but the AMS URL was not independently verified.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).

Conjecture. Every simple $d$-regular graph on $n$ vertices with $n$ even and $d \ge n/2$ is $d$-edge-colourable.

Context

Equivalently, such graphs have a 1-factorization. Usually stated (Chetwynd and Hilton 1985) with the sharper threshold $d \ge 2\lceil n/4 \rceil - 1$.

Related records in this index

This conjecture was absent from the Open Problem Garden and arXiv corpora; the records below are the nearest ones.

Goldberg's conjecture — overfull parameter and chromatic index

Editorial notes. Editorial lead, to be confirmed by the status review: Csaba, Kühn, Lo, Osthus and Treglown, 'Proof of the 1-factorization and Hamilton decomposition conjectures', Mem. Amer. Math. Soc. 244 (2016), for sufficiently large $n$.

Source

Théorie des graphes (J.A. Bondy, U.S.R. Murty; French edition by Frédéric Havet, 2025), Appendix A « Problèmes ouverts »
Item 57, book p. 631 (PDF p. 647) · https://inria.hal.science/hal-05211979v1 · PDF
English edition: J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer 2008, Appendix A.