A near-linear Chvátal--Erdős condition for Hamilton cycles in digraphs
For a digraph $D$, let $α_2(D)$ be the largest size of a vertex set containing no directed $2$-cycle. Let $f_2(a)$ be the least positive integer $k$ such that every $k$-strongly connected digraph $D$ with $α_2(D)\le a$ has a Hamilton cycle. Jackson and Ordaz conjectured that $f_2(a)\le a+1$. Towards this conjecture, we establish the near-linear bound $f_2(a)=O\!\left(\frac{a(\log a)^4}{(\log\log a)^2}\right),$ and hence $f_2(a)=O_\varepsilon(a^{1+\varepsilon})$ for every fixed $\varepsilon>0$. We also disprove the pancyclicity conjecture of Jackson and Ordaz that every digraph $D$ with…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.10292
curl -X POST /api/v1/records/arxiv/2610.10292/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.10292/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'