Conjectured threshold for powers of Hamilton cycles
Conjectured threshold for powers of Hamilton cycles
Let denote the graph parameter used in the source, and let be an -vertex graph with minimum degree and independence number . The -th power of a Hamilton cycle is obtained by joining every pair of vertices at cyclic distance at most on a Hamilton cycle.
Connecting-barrier conjecture. Given and , there exists such that the following holds for sufficiently large . If
and
then contains an -th power of a Hamilton cycle.
The conjecture is motivated by a construction called the connecting barrier, which gives a matching asymptotic lower bound in the source for . Its resolution status is not specified here.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ming Chen, Jie Han, Yantao Tang and Donglei Yang, “On powers of Hamilton cycles in Ramsey-Turán Theory”, arXiv:2305.17360 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.