← All problems

Kotzig's conjecture and Wormald's random-regular-graph conjecture

For every integer m≥2m\ge 2, the complete graph K2mK_{2m} has a decomposition E(K2m)=M1⊔⋯⊔M2m−1E(K_{2m})=M_1\sqcup\cdots\sqcup M_{2m-1} into perfect matchings such that, for every pair i≠ji\ne j, the graph with edge set Mi∪MjM_i\cup M_j is a Hamiltonian cycle.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A November 2026 report claims a sharp threshold for a random-graph version, but neither the complete-graph conjecture nor the random-regular-graph conjecture is settled.

The problem combines Kotzig’s 1963 conjecture that KnK_n has a perfect 11-factorisation with Wormald’s conjecture that random fixed-degree regular graphs have one asymptotically almost surely. Both exact conjectures remain open.

Known results

  • For fixed kk, Glock and Sgueglia (2025) proved that G(n,p)G(n,p) typically contains kk edge-disjoint perfect matchings with pairwise Hamiltonian unions when p≥C(k)log⁡n/np\geq C(k)\log n/n.
  • Glock and Sgueglia (2025) obtained corresponding extension-counting estimates and a deterministic extension theorem under a non-overlap condition.
  • A 2026 preprint constructs asymptotically almost all of a complete-graph factorisation with the pairwise Hamiltonian property, but not an exact solution.

November 2026 hitting-time claim

Glock, Lichev, and Sgueglia report a sharp hitting-time theorem for every fixed kk in the binomial random-graph process. The retrieved literature does not independently corroborate this claim; the earlier paper instead lists the hitting-time statement as open. It is progress on a random-graph variant, not a solution of either exact conjecture.

Current status (as of November 2026): The complete-graph and random-regular-graph conjectures remain open; a sharper random-graph hitting-time result is claimed but unverified.

Sources

Solutions 0

No solutions have been posted yet.