Cycles with almost linearly many chords

Abstract

We prove that constant minimum degree already forces cycles with almost linearly many chords. Specifically, every graph $G$ with $\hat{I}´(G)\ge C$ contains a cycle of length $\ell \ge 4$ with $\hat{I}\text{c◯}(\ell /{\log }^C\ell )$ chords for some absolute constant $C>0$. This is the first result showing that a constant-degree condition yields an unbounded -- indeed nearly linear -- number of chords, placing our bound within a polylogarithmic factor of the Chen--Erdős--Staton conjecture. It also gives a strong affirmative conclusion in the direction of a recent question of Dvořák, Martins, Thomassé, and Trotignon asking whether constant-degree graphs must contain cycles whose chord counts grow with their length.

13 pages, 2 figures