pith. sign in

arxiv: 2606.08401 · v1 · pith:U3I2J2R6new · submitted 2026-06-07 · 🧮 math.CO

A cubic refinement of Jackson's Chv\'atal--ErdH{o}s condition for Hamilton cycles in digraphs

classification 🧮 math.CO
keywords boundatwocycledigraphhamiltonjacksonpolynomialasked
0
0 comments X
read the original abstract

For a digraph $D$, let $\aTwo(D)$ be the largest size of a vertex set no two of whose vertices lie in a common directed $2$-cycle. Let $f_2(a)$ be the least integer $K$ such that every $K$-connected digraph $D$ with $\aTwo(D)\leq a$ has a Hamilton cycle. In 1987, Jackson proved that $f_2(a)\leq 2^a(a+2)!$ and asked for better bounds, noting that a linear bound might be possible. K\"uhn and Osthus later observed that even a polynomial bound would be interesting. In this short note, we prove the polynomial bound $f_2(a)\leq 2a^3+2$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.