Chvátal's toughness conjecture

Status partial high confidence

Chvátal's toughness conjecture remains open in full generality as of September 2026. If the conjecture is true, the constant k must satisfy k ≥ 9/4 (a lower bound from Bauer, Broersma, and Veldman via non-Hamiltonian (9/4−ε)-tough graphs). The conjecture has been verified for several special graph classes: chordal graphs (k=10 suffices, Kabela–Kaiser 2015), claw-free graphs, planar graphs, and various forbidden-subgraph-free families addressed in a sequence of recent papers through 2026. No counterexample to the general existential statement is known, and no proof for general graphs has been found.

Cited literature (3)

• partial 10-tough chordal graphs are Hamiltonian (2015)
  Kabela, Kaiser · arXiv preprint · arXiv:1508.02568

  Every 10-tough chordal graph is Hamiltonian (and Hamilton-connected), improving the prior bound of 18 (Chen et al.) and verifying Chvátal's conjecture for chordal graphs with explicit constant k=10.

• partial Hamiltonian cycles in tough (P₄∪P₁)-free graphs (2025)
  not extracted from fetch · arXiv preprint · arXiv:2504.08936

  Every 23-tough (P₄∪P₁)-free graph on at least three vertices is Hamiltonian, verifying Chvátal's conjecture for this forbidden-subgraph class with k=23.

• partial Toughness Bounds for Fractional Hamiltonicity and Resistance Positivity (2026)
  not extracted from fetch · arXiv preprint · arXiv:2609.03412

  Every 10-tough graph is fractionally Hamiltonian; this verifies an analog of Chvátal's conjecture for the fractional relaxation (a weaker property than Hamiltonicity), but does not resolve the original conjecture.

Reviewer notes. The conjecture as stated asks for existence of a positive integer k; this has been neither proved nor disproved for general graphs. The best known lower bound on k (if the conjecture is true) is 9/4, due to Bauer, Broersma, and Veldman (non-Hamiltonian (9/4−ε)-tough graphs for all ε>0). Verified special classes include: claw-free graphs (Enomoto et al., 1998, k=1 suffices for a strengthening), planar graphs (Böhme, Harant, Tkáč, 1999, k=4), chordal graphs (Kabela–Kaiser, arXiv:1508.02568, k=10), and numerous forbidden-subgraph-free families in recent 2024–2026 papers. A separate conjecture by Haemers on a spectral lower bound for toughness was proved in arXiv:2605.15738 (2026) but concerns a different statement unrelated to Hamiltonicity. Hoàng's degree-sequence conjecture for t-tough graphs (arXiv:2503.14735, 2025, verified for t≥4) is a related but distinct open problem. The general existential statement of Chvátal's conjecture remains open with no announced breakthrough found in this search.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).