The 1-factorization conjecture for regular graphs

About 11 years old · traced to 2015

Let $G$ be a regular graph of even order. The 1-factorization conjecture. Every regular graph of even order with sufficiently high degree is $1$ -factorizable. Here, $1$ -factorizable means that the edge set of $G$ can be decomposed into perfect matchings. This conjecture concerns the threshold at which regular graphs admit an edge decomposition into perfect matchings; the source does not provide enough information here to determine whether it has been resolved.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

The 1-factorization conjecture for regular graphs
Let $G$ be an $N$ -regular graph with $2n$ vertices. A 1-factorization is a decomposition of the edges of $G$ into perfect matchings. The 1-factorization conjecture. If $n$ is odd and $N\geq n$ , or if $n$ is even and $N\geq n-1$ , then $G$ has a 1-factorization. This conjecture gives degree thresholds guaranteeing 1-factorizations beyond the bipartite case; the source presents it as a related general conjecture, without stating a resolution.
source: Robert W. Donley, S. James Gates, Tristan Hübsch and Rishi Nath, “A combinatorial introduction to Adinkras”, arXiv:2410.12834 (2024).

References

Primary source

Hongliang Lu and David G. L. Wang, “The maximum number of perfect matchings of semi-regular graphs”, arXiv:1509.00569 (2015).

Posted 1 month ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.