Cycle lengths and chords under chromatic and degree constraints

Abstract

We mainly consider three problems on cycle lengths and cycles with chords in graphs: (a) Gao, Huo, and Ma \cite[Question~1.5]{GaoHuoMa2021} asked whether, for every fixed $k\ge3$, there is a function $f_k(n)\to\infty$ such that every $n$-vertex $(k+1)$-critical graph contains $f_k(n)$ consecutive cycle lengths. (b) Let $g_k(n)$ be the maximum integer $t$ such that every $n$-vertex $k$-critical graph with $k\ge4$ contains an odd cycle with at least $t$ chords. Voss conjectured (see \cite[pp.~168]{VossBook}) that $g_k(n)\to\infty$ as $n\to\infty$ for each $k\ge4$, which extends a 1976 conjecture of Erdős (see also Erdős Problem~1091 \cite{Bloom1091}). (c) Kára and Král \cite{KaraKral2003} conjectured that every graph on $31$ vertices with minimum degree at least $8$ contains a cycle with at least $31$ chords. We answer question (a) in the negative for $k=3$, and disprove conjecture (b) for all $k\ge5$. We point out the work of Alexeev-Putterman-Sawhney-Sellke-Valiant (2026) on Erdős Problem 1901 disproves the case $k=4$ for conjecture (b). We prove conjecture (c). We also discuss two other related problems in the part of concluding remark.

Disclosure

“nt The second author is grateful to Jie Ma for providing the reference [2] and for introducing him to the Erdős Problems website. The authors also thank Thomas Bloom for creating and sustaining the website [4]. Declaration of AI usage An AI assistant (Chatgpt 5.5) was used in the search for a construction in Theorem 1.2 with the initial requirement based on the Hajós join suggested by the second author. After several rounds of refinement, talks with AI and checking, we have the current”

PDF page 17

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:56:19.347175Z

Structural counts