Logarithmic Circumference In Tough Graphs

Abstract

For every real $t>0$, we prove that every $2$-connected $t$-tough graph contains a cycle of length at least $\ell$ whenever $n\le \ell (1+1/t{)}^{\lfloor \ell /2\rfloor -1}$. This establishes the logarithmic bound conjectured by Broersma, van den Heuvel, Jung, and Veldman.

6 pages