Xiao-Zheng Chen

On Erd\H{o}s Problem 767: Cycles with Chords

For integers $k\ge 1$ and $n\ge k+2$, let $g_k(n)$ be the maximum number of edges in an $n$-vertex graph containing no cycle with a vertex incident with at least $k$ chords. Erd\H{o}s conjectured that $g_k(n)=(k+1)(n-k-1)$ for $n\ge 2k+2$. Lewin found a counterexample. Bollob\'as later conjectured that there exists a f...