Colour-balanced Hamilton cycle bounds in complete graphs
Problem 6.4 · arXiv:2604.09449
Status open high confidence
Problem 6.4 asks to improve the O(k^2) upper bound on f_h(H) for a Hamilton cycle H in complete or complete bipartite graphs. The source paper establishes this bound via a necklace-splitting argument, noting that any improvement to the bipartite matching bound yields an equal improvement for complete graphs. The paper was posted in April 2026, and no follow-up work addressing this problem has been found in the literature.
Reviewer notes. No follow-up found. The paper was posted 2026-04-10 and as of 2026-05-14 is only ~5 weeks old; absence of follow-up is expected. The conjecture is tightly coupled to the bipartite matching bound via necklace-splitting, so progress on either sub-problem would resolve both.
Context
The general upper bound from Theorem 1.2 gives $O(k^2)$ for Hamilton cycles in complete graphs, and the same bound holds for complete bipartite graphs by the paper's methods. A necklace-splitting argument shows any improvement to the bipartite matching bound yields an equal improvement here, so progress on either problem benefits the other.
Source paper
Colour-balanced subgraphs
Emma Hogan, Alex Scott, Dmitry Tsarev · 2026-04-10
https://arxiv.org/abs/2604.09449