A cubic refinement of Jackson's Chv\'atal--ErdH{o}s condition for Hamilton cycles in digraphs
classification
🧮 math.CO
keywords
boundatwocycledigraphhamiltonjacksonpolynomialasked
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.