pipette
ESEspañol

Linear circumference in vertex-transitive graphs

Jie Ma, Ziyuan Zhao

PreprintClaims a big step

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.