pipette
ESEspañol

A near-linear Chv\'atal--Erd\H{o}s condition for Hamilton cycles in digraphs

Chengli Li, Bo Ning

Preprint

In the authors' words

For a digraph , let be the largest size of a vertex set containing no directed -cycle. Let be the least positive integer such that every -strongly connected digraph with has a Hamilton cycle. Jackson and Ordaz conjectured that . Towards this conjecture, we establish the near-linear bound and hence for every fixed . We also disprove the pancyclicity conjecture of Jackson and Ordaz that every digraph with contains a directed cycle of every length from to .

Main resultLimitation the authors admit

Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.