2026/07/16 by Xiaozheng Chen, Bo Ning
#math.CO
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≥3, there is a function fk(n)→∞ such that every n-vertex (k+1)-critical graph contains fk(n) consecutive cycle lengths. (b) Let gk(n) be the maximum integer t such that every n-vertex k-critical graph with k≥4 contains an odd cycle with at least t chords. Voss conjectured (see \cite[pp.~168]VossBook) that gk(n)→∞ as n→∞ for each k≥4, which extends a 1976 conjecture of Erdős (see also Erdős Problem~1091 \citeBloom1091). (c) Kára and Král \citeKaraKral2003 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≥5. 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.