Linear circumference in vertex-transitive graphs
In the authors' words
We prove that there is an absolute constant such that every connected vertex-transitive graph on vertices contains a cycle of length at least . Moreover, every such graph with sufficiently large degree contains a cycle of length at least . This gives the first linear bound towards Lov\'asz's Hamiltonicity conjecture. The proof combines a structural result of DeVos and Mohar on vertex-transitive graphs with a general framework for finding long cycles, which may be of independent interest.
Main resultLimitation the authors admit
Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.