Hoàng's degree-sequence conjecture for tough graphs

About 3 years old · traced to

Let GG be a simple graph. Write c(G)c(G) for its number of components, and define its toughness by

τ(G)=min⁡{∣S∣c(G−S):S⊆V(G), c(G−S)≥2}\tau(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G),\ c(G-S)\ge 2\right\}

when GG is not complete, with τ(G)=∞\tau(G)=\infty otherwise. The graph is tt-tough if τ(G)≥t\tau(G)\ge t. Let d1≤d2≤⋯≤dnd_1\le d_2\le\cdots\le d_n be the degree sequence of an nn-vertex graph GG.

Hoàng's conjecture. Let n≥3n\ge 3 and t≥1t\ge 1 be integers. If GG is tt-tough and, for every i<n2i<\frac n2, di≤id_i\le i implies dn−i+t≥n−id_{n-i+t}\ge n-i, then GG is Hamiltonian.

This conjecture is a toughness analogue of Chvátal's degree-sequence theorem. Hoàng proved it for t≤3t\le 3, Hoàng and Robin proved it for t=4t=4, and the source states that it has been confirmed for all t≥4t\ge 4; thus the conjecture is solved.

References

Primary source

Songling Shan and Arthur Tanyel, “A strengthening of a degree sequence condition for Hamiltonicity in tough graphs”, arXiv:2503.14735 (2025).

Additional references

2 papers in this index state this conjecture (2023–2025). The statement above is taken from the most recent of them; the others are arXiv:2303.03479.

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.