Delphi.science

Chvátal's Toughness Conjecture for Dense Almost Regular Graphs

Source: arxiv.org/abs/2611.12519

Songling Shan

arXivarxiv/2611.12519Nov 9, 2026math.COscore 0

Chvátal's toughness conjecture asserts that there is a constant $t_0$ such that every $t_0$-tough graph on at least three vertices is Hamiltonian. Most partial results on this conjecture concern graphs with a restricted structure, such as chordal graphs and $H$-free graphs for small linear forests $H$. We confirm the conjecture with $t_0=4$ for dense almost regular graphs, without any structural assumption: for every $α>0$, there exist $\varepsilon>0$ and $n_0$ such that every $4$-tough graph $G$ on $n\ge n_0$ vertices with $δ(G)\geαn$ and $Δ(G)-δ(G)\le\varepsilon n$ is Hamiltonian. This…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.12519
curl -X POST /api/v1/records/arxiv/2611.12519/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.12519/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'