Square Hamilton cycle conjecture for graphs with sublinear independence number

Let ε>0\varepsilon>0. A graph GG has independence number α(G)\alpha(G) equal to the maximum size of a set of pairwise nonadjacent vertices, and the square of a Hamilton cycle is the graph obtained from a Hamilton cycle by joining every pair of vertices at distance at most two on the cycle. Square Hamilton cycle conjecture. There exist γ>0\gamma>0 and n0Nn_0\in\mathbb{N} such that, for every nn-vertex graph GG with nn0n\geq n_0, if

δ(G)(1/2+ε)nandα(G)γn,\delta(G)\geq (1/2+\varepsilon)n \quad\text{and}\quad \alpha(G)\leq \gamma n,

then GG contains the square of a Hamilton cycle. This would strengthen the known triangle-factor result for graphs with the same minimum-degree and independence-number conditions, and is posed as a natural next step toward a bandwidth theorem for graphs with sublinear independence number.

Sources & referencesView supporting material

Primary source

Katherine Staden and Andrew Treglown, “The bandwidth theorem for locally dense graphs”, arXiv:1807.09668 (2020).

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.

Solutions 0

No solutions have been posted yet.