Cycle lengths and chords under chromatic and degree constraints

Bo Ning; Xiaozheng Chen

REVIEW 3 major objections 4 minor 22 references

Cycle lengths and chords under chromatic and degree constraints

T0 review · 3 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper settles three old questions about cycle chords and lengths in critical graphs: the 31-vertex/31-chord conjecture is true, and two growth conjectures fail.

desk verdict Strong paper with real results and a clear fix needed: the Kára–Král proof rests on an unproved 'distilled' lemma, and one side proof is garbled. read the letter →

arxiv 2607.15501 v1 pith:DCD7QKUZ submitted 2026-07-16 math.CO

Xiaozheng Chen , Bo Ning This is my paper · ORCID

classification math.CO MSC 05C1505C3505C38

keywords k-criticalgraphscyclelengthschordsminimumdegreeconsecutiveblockdecompositionchromaticnumberHamiltoniancycles

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper answers three standing questions about how chromatic number, criticality, and minimum degree force cycles with many chords or long runs of consecutive lengths. It shows that the consecutive-cycle-length question fails already for k=3: there are 4-critical graphs of arbitrarily large order whose cycle lengths contain no interval of more than four consecutive integers. It refutes the conjecture that every large k-critical graph must contain an odd cycle with arbitrarily many chords, by building k-critical graphs of unbounded order in which every cycle has a number of chords bounded by a constant depending only on k. It proves the 31-vertex/31-chord conjecture in the affirmative, showing that minimum degree 8 is exactly the threshold. A reader should care because the results draw sharp lines around how much structural regularity chromatic-number conditions can force.

What carries the argument

The three results use different engines. For k=3, the machine is a recursive chain of joins of copies of K4: at each step a new triangle is grafted onto a distinguished terminal edge, and recurrences for the sets of terminal-path lengths and cycle lengths give the exact formula L(G_t)={3,4}∪{5+3i,6+3i:0≤i≤t−2}∪{3t+1}, whose gaps (7+3i) cap ρ(G_t) at 4. For bounded chords, the graph H_{k,m} layers a clique of size k−3, a chain of m+1 spine pentagons, and pendant pentagons attached to spine vertices; each leaf forces a spine vertex to avoid a clique color, yielding k-criticality, while cycles can meet few leaf pentagons, bounding the chord count by binom(k−3,2)+10(k−3)^2+60(k−3). For f(31,31),

What would settle it

Find a 2-connected non-Hamiltonian graph G with a terminal-cycle setup in which u1 and u_{m−1} are accessible and every accessible vertex has degree at least d inside H, yet G has no cycle with d(d−2) chords; such a graph would invalidate the terminal-cycle lemma and the theorem f(31,31)=8.

Watch

Extended reading notes

Core claim

In the paper's own terms, the central claim is a triple conclusion. First, for k=3, the consecutive-cycle-length question has a negative answer: there are 4-critical graphs G_t of order 3t+1 whose cycle lengths avoid arbitrarily long intervals; in fact, the largest run of consecutive cycle lengths, ρ(G_t), is at most 4 for all t≥3. Second, for every k≥4 there are infinitely many k-critical graphs in which every cycle has at most binom(k−3,2)+10(k−3)^2+60(k−3) chords, so the chord-growth conjecture for k-critical graphs is false. Third, every 31-vertex graph with minimum degree at least 8 contains a cycle with at least 31 chords, and minimum degree 7 does not suffice; hence f(31,31)=8. The pa

Load-bearing premise

The proof of the 31-vertex theorem depends on a terminal-cycle lemma imported from a 1985 proof rather than proved here; if that lemma's distilled statement is wrong or incomplete, the non-Hamiltonian case—and with it the f(31,31)=8 upper bound—collapses.

Editorial extensions

If this is right

For k=3, the consecutive-cycle-length question is closed: no function f_3(n) exists, since the 4-critical graphs G_t have ρ(G_t)≤4.
For every k≥4 there are k-critical graphs of arbitrarily large order with at most binom(k−3,2)+10(k−3)^2+60(k−3) chords on every cycle, so the chord-growth conjecture is false.
The extremal function f(31,31) equals 8: minimum degree 8 suffices and minimum degree 7 does not.
Every K4-free graph with chromatic number at least 4 has a cycle with at least four chords.
The H_{k,m} construction recovers the earlier k=4 counterexample under relabeling, so the bounded-chord phenomenon is uniform across k≥4.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the recursive-join construction used for k=3 is likely adaptable to higher k by joining copies of K_{k+1}; if so the negative answer to the consecutive-length question would extend beyond k=3, a step the paper does not take.
Editorial inference: the chord bound for H_{k,m} grows quadratically in k; whether the true maximum chord count in k-critical graphs is linear in k is a natural open problem.
Editorial inference: the block-closure argument for the 31-vertex theorem may be parameterizable to other small pairs (n,c), giving exact values of f(n,c) for nearby parameters, though the authors only establish (31,31).
Editorial inference: the K4-free four-chord result, combined with the pentagonal-wheel example, suggests a threshold phenomenon for K_r-free critical graphs that could be tested computationally for r≥5.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Main thing to know: this is a strong, substantial paper that resolves several open problems, but it is not ready to publish as is. The k=3 negative answer to Gao–Huo–Ma and the k≥5 counterexamples to Voss's conjecture are well-built and check out; the Kára–Král proof is the part that needs work.

The Hajós construction in Section 2 is clean. I checked the recurrence in Lemmas 2.3–2.4 and the resulting cycle-length set; it indeed gives ρ(G_t)=4 for all t≥3, which kills Problem 1.1 for k=3. The H_{k,m} construction in Section 3 is also solid: the leaf-forcing argument in Lemma 3.2 is convincing, criticality follows from the degree counts and cactus coloring, and the chord-counting in Lemma 3.8 is careful. The bound depends only on k, so Voss's conjecture is false for every k≥5. The k=4 case is attributed to Alexeev et al.; the paper says H_{4,m} is isomorphic to their graph, which I did not verify, but that is not load-bearing for k≥5.

The real issue is Theorem 1.12. The proof is a chain, and one load-bearing link, Lemma 4.3, is not proved. The paper states it is "distilled from the proof of Ash's Theorem 1." That is not enough for a referee. Lemma 4.3 is non-obvious and its hypotheses involve accessible vertices in a terminal cycle while the conclusion is a chord-rich cycle in the whole graph. If the distillation has dropped a hypothesis, the |Q(B*)|≥14 branch of Proposition 4.8 fails and Theorem 4.10—and hence f(31,31)=8—collapses. The authors need either to prove Lemma 4.3 or to cite a precise lemma from Ash with a location.

There is also a genuine garble in Lemma 5.3 (used for Proposition 1.13): the proof says δ(G)≥3 implies Δ(G)≤2, which is false in G; the argument is being run in the complement. The result itself—the six-vertex K4-free 4-critical graph is the wheel—is true, but the proof as printed is not usable.

One stress-test concern I checked did not land: the alleged bad Hamilton cycle in Claim 4.1 of Lemma 4.6. The cycle a x b c y d P1 a uses the edge b-c, which is present because H[Q] is a clique after closure; it does not use the supposedly missing edge b-y. That part is fine.

Who is this for? People working on chromatic-critical graphs, cycle lengths, and chorded cycles. It deserves a serious referee, but the referee will need to inspect Ash's paper. My recommendation: send it to peer review, and require the authors to prove or precisely cite Lemma 4.3 and to repair Lemma 5.3 before acceptance.

Referee Report

3 major / 4 minor

Summary. The paper addresses three questions relating chromatic number or minimum degree to cycle lengths and chords. It first gives a negative answer to a question of Gao–Huo–Ma for k=3 by constructing 4-critical graphs G_t of order 3t+1 whose cycle-length sets contain no interval longer than 4 (Theorems 1.2 and 2.5). Second, it constructs k-critical graphs H_{k,m} with linearly many vertices but only O_k(1) chords on every cycle for every k≥4, thereby disproving a conjecture of Voss for k≥5 and, using the cited construction of Alexeev et al., also for k=4 (Theorem 1.6). Third, it proves the Kára–Král conjecture f(31,31)=8 (Theorem 1.12) by proving a degree-refined theorem (Theorem 1.11) and then carrying out a block-level extremal analysis. A final section proves a result on K4-free 4-chromatic graphs and gives an infinite family refuting a separate conjecture of Voss on 3-connected graphs.

Significance. If fully correct, this is a substantial paper. The k=3 negative answer and the Voss-conjecture counterexamples are cleanly demonstrated: the Hajós construction is elementary, the criticality proof is explicit, and the chord bound in Lemma 3.8 is explicit and constant in the order of the graph. The k=4 case is properly attributed to Alexeev et al., with the present contribution being the extension to all k≥5. The Kára–Král theorem is a significant extremal result, and the block decomposition in Propositions 4.8–4.9 appears carefully designed. However, the proof of Theorem 1.12 currently depends on an unproved imported lemma (Lemma 4.3), and another proof in the same section contains an invalid displayed cycle. These must be repaired before the paper can be considered correct as a self-contained contribution.

major comments (3)

[Section 4.1, Lemma 4.3] The terminal-cycle lemma is not proved in the paper; it is only said to be 'distilled' from Ash's proof, with no page or lemma number. This lemma is load-bearing: the non-Hamiltonian case of Theorem 1.11 is exactly Lemma 4.3, Proposition 4.8 applies Theorem 1.11 in the branch |Q(B*)|≥14, and Theorem 4.10 relies on Proposition 4.8. The statement is not immediate: it concludes from accessibility of u1,u_{m-1} and degree conditions on W(H) that G contains a cycle with d(d−2) chords, even though the terminal-cycle setup leaves vertices of P outside H. The manuscript provides no way to rule out dropped hypotheses on |W(H)|, m, or 2-connectivity. Please supply a complete proof, or quote Ash's argument in sufficient detail and verify that the distilled statement is correct.
[Section 5.1, Lemma 5.3] The proof of Lemma 5.3 silently changes G to its complement. It asserts that 'Since δ(G)≥3, we have ∆(G)≤2' and later that 'G is triangle-free'; both assertions are false for the intended 6-vertex graph, the wheel W5, which has ∆=5 and contains triangles. The intended argument is coherent only if the unbarred graph is the complement throughout the proof. Please rewrite with explicit complement notation, re-check the matching and coloring arguments, and ensure the conclusion 'contains a cycle with four chords' is drawn for the original graph. As printed, the proof cannot be followed.
[Section 4.2, Lemma 4.6, Claim 4.1] In the subcase X∩Y=∅, the displayed cycle 'a x b y c d P1 a' uses the edge b y, which is not guaranteed (b∈X, but y is not necessarily adjacent to b). The claim is probably repairable—for instance, take a Hamilton path in Q from b to c and finish with the edge d a—but as written the construction is invalid. Please correct the cycle and re-verify the rest of the case analysis, since Lemma 4.6 is used in Proposition 4.9.

minor comments (4)

[Page 3, after Theorem 1.5] The sentence 'our graph H4,m is isomorphic to their graph Gm m' should read 'G_m'.
[Page 9, terminal-cycle setup] The phrase 'select one that maximizes the length of the terminal cycle defined below' refers to an object not yet defined. Define the terminal cycle before the maximization, or state the choice criterion more formally.
[Page 12, Lemma 4.7] In the inequality |E(B*)| ≥ (8q(B*) + d_{B*}(x))/2, the degree d_{B*}(x) is inside B*, not in G. The surrounding text implies this, but an explicit sentence would avoid confusion, especially because x is a cut vertex of G.
[References] The cited arXiv item [2] and the erdosproblems.com link are acceptable, but if a published version of [2] becomes available it should be cited in the standard way.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's derivations are self-contained or rely on independent published results (Hajós, Bondy–Chvátal, Ash, Gupta–Kahn–Robertson, Tian–Zang), with no fitted parameters, no self-citation, and no definitional equivalences.

full rationale

I walked the main derivation chains: (i) Theorem 1.2 constructs G_t via Hajós joins and explicitly computes L(G_t) in Theorem 2.5; there is no fitted quantity or hidden definitional equivalence. (ii) Theorem 1.6 constructs H_{k,m} and bounds chords directly in Lemma 3.8; the counting is explicit and does not presuppose the conclusion. (iii) Theorem 1.12 is proved by a block-cut analysis (Propositions 4.8, 4.9, Theorem 4.10) whose tools are either proved in the paper or cited from independent literature: Ash's Theorem 1.8, Gupta–Kahn–Robertson Theorem 1.7, Tian–Zang Theorem 1.9, and Bondy–Chvátal Theorem 4.5. The non-Hamiltonian half of Theorem 1.11 rests on Lemma 4.3, which is imported from Ash's proof; this is external support, not a self-citation, and not a reduction of the theorem to its own hypothesis. The paper contains no self-citations by the authors, no fitting of parameters to data that is then called a prediction, and no ansatz disguised as derivation. The skeptical concerns about Lemma 4.3 being unproved in this text and about Claim 4.1's Hamilton-cycle construction being possibly garbled are correctness/verification risks, not circularity: even if Lemma 4.3's statement were incomplete, that would be a gap in external support, not an equivalence between input and output. Because the central claims do not reduce to their inputs by construction, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

Everything rests on standard cited theorems and explicit finite constructions. There are no fitted constants, no ad hoc parameters, and no invented entities. The least transparent input is Lemma 4.3, which is stated as distilled from Ash's proof rather than proved in the paper.

assumptions (6)

standard math Hajós join of two r-critical graphs is r-critical (Fact 2.1)
Used in Proposition 2.2 to build the 4-critical family G_t for Theorem 1.2.
standard math Every cactus is 3-colorable (Fact 3.5)
Used in Lemma 3.6 to show H_{k,m} is k-colorable after deleting the clique Q.
standard math Bondy–Chvátal closure theorem (Theorem 4.5)
Used throughout Section 4 to infer Hamiltonicity from closures in Lemmas 4.6 and 4.7 and Proposition 4.8.
standard math Terminal-cycle lemma, distilled from Ash's proof (Lemma 4.3)
Imported from Ash's proof of Theorem 1.8; it carries the non-Hamiltonian case of Theorem 1.11, hence part of the Kára–Král proof.
standard math Gupta–Kahn–Robertson theorem and Tian–Zang theorem (Theorems 1.7 and 1.9)
Used in the concluding side result Proposition 1.13, not in the main Kára–Král proof.
domain assumption Alexeev–Putterman–Sawhney–Sellke–Valiant Theorem 4.1 (Theorem 1.5)
Cited for the sharper k=4 disproof of Voss's conjecture; the paper's own Theorem 1.6 covers k≥4 independently.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Cycle lengths and chords under chromatic and degree constraints." pith.science (2026). https://pith.science/paper/DCD7QKUZ

@misc{pith2026260715501,
  author       = {Pith},
  title        = {Pith review of: Cycle lengths and chords under chromatic and degree constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DCD7QKUZ}},
  note         = {Machine review of arXiv:2607.15501}
}

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\H{o}s (see also Erd\H{o}s Problem~1091 \cite{Bloom1091}). (c) K\'ara and Kr\'al \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\H{o}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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 1 linked inside Pith

[1]

Ash, The maximum number of diagonals of a cycle in a block,Discrete Math.55(1985), 305–309

P. Ash, The maximum number of diagonals of a cycle in a block,Discrete Math.55(1985), 305–309

1985
[2]

Alexeev, M

B. Alexeev, M. Putterman, M. Sawhney, M. Sellke, and G. Valiant, Short proofs in combinatorics, probability and number theory II, arXiv:2604.06609 (2026)

arXiv 2026
[3]

Bondy, V

J.A. Bondy, V. Chvátal, A method in graph theory,Discrete Math.15(1976), no. 2, 111–135

1976
[4]

T. F. Bloom, Erdős Problem #1091,https://www.erdosproblems.com/1091, accessed 11 June 2026

2026
[5]

P. Erdős, Some recent problems and results in graph theory, combinatorics and number theory, inProceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing(Louisiana State University, Baton Rouge, La., 1976), Congressus Numerantium XVII, Utilitas Math., Winnipeg, 1976, pp. 3–14. 17

1976
[6]

Erdős, Some of my favourite unsolved problems, in: A

P. Erdős, Some of my favourite unsolved problems, in: A. Baker, B. Bollobás, A. Hajnal (Eds), A Tribute to Paul Erdős,Cambridge University Press, Cambridge, 1990, pp. 467–478

1990
[7]

Erdős, Some of my favourite problems in various branches of combinatorics,Matematiche (Catania),47(1992), 231–240

P. Erdős, Some of my favourite problems in various branches of combinatorics,Matematiche (Catania),47(1992), 231–240

1992
[8]

J. Gao, Q. Huo, C.-H. Liu, and J. Ma, A unified proof of conjectures on cycle lengths in graphs,Int. Math. Res. Not.2022(2022), no. 10, 7615–7653

2022

Show all 22 references

[9]

J. Gao, Q. Huo, and J. Ma, A strengthening on odd cycles in graphs of given chromatic number,SIAM J. Discrete Math.35(2021), no. 4, 2317–2327

2021
[10]

R. P. Gupta, J. Kahn, and N. Robertson, On the maximum number of diagonals of a circuit in a graph,Discrete Math.32(1980), 37–43

1980
[11]

Gyárfás, Graphs withkodd cycle lengths,Discrete Math.103(1992), 41–48

A. Gyárfás, Graphs withkodd cycle lengths,Discrete Math.103(1992), 41–48

1992
[12]

G. Hajós, Über eine Konstruktion nichtn-färbbarer Graphen,Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe10(1961), 116–117

1961
[13]

T. R. Jensen and G. F. Royle, Hajós constructions of critical graphs,J. Graph Theory30 (1999), no. 1, 37–50

1999
[14]

T. R. Jensen and B. Toft,Graph Coloring Problems, Wiley-Interscience, New York, 1995

1995
[15]

Kára and D

J. Kára and D. Král, Minimum degree and the number of chords,Ars Combin.68(2003), 169–179

2003
[16]

Kostochka, B

A. Kostochka, B. Sudakov, and J. Verstraëte, Cycles in triangle-free graphs of large chromatic number,Combinatorica37(2017), 481–494

2017
[17]

J. A. Larson, Some graphs with chromatic number three,J. Combin. Theory, Ser. B26 (1979), 317–322

1979
[18]

Mihók and I

P. Mihók and I. Schiermeyer, Cycle lengths and chromatic number of graphs,Discrete Math.286(2004), 147–149

2004
[19]

Sudakov and J

B. Sudakov and J. Verstraëte, The extremal function for cycles of lengthl mod k,Electron. J. Combin.24(1)(2017), #P1.7

2017
[20]

Tian and W

F. Tian and W. Zang, The maximum number of diagonals of a cycle in a block and its extremal graphs,Discrete Math.89(1991), 51–63

1991
[21]

Voss, Graphs having circuits with at least two chords,J

H.-J. Voss, Graphs having circuits with at least two chords,J. Combin. Theory, Ser. B32 (1982), 264–285

1982
[22]

Voss,Cycles and Bridges in Graphs, Kluwer Academic Publishers, Dordrecht, and VEB Deutscher Verlag der Wissenschaften, Berlin, 1991

H.-J. Voss,Cycles and Bridges in Graphs, Kluwer Academic Publishers, Dordrecht, and VEB Deutscher Verlag der Wissenschaften, Berlin, 1991. 18

1991

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

Ash, The maximum number of diagonals of a cycle in a block,Discrete Math.55(1985), 305–309

P. Ash, The maximum number of diagonals of a cycle in a block,Discrete Math.55(1985), 305–309

1985

[2] [2]

Alexeev, M

B. Alexeev, M. Putterman, M. Sawhney, M. Sellke, and G. Valiant, Short proofs in combinatorics, probability and number theory II, arXiv:2604.06609 (2026)

arXiv 2026

[3] [3]

Bondy, V

J.A. Bondy, V. Chvátal, A method in graph theory,Discrete Math.15(1976), no. 2, 111–135

1976

[4] [4]

T. F. Bloom, Erdős Problem #1091,https://www.erdosproblems.com/1091, accessed 11 June 2026

2026

[5] [5]

P. Erdős, Some recent problems and results in graph theory, combinatorics and number theory, inProceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing(Louisiana State University, Baton Rouge, La., 1976), Congressus Numerantium XVII, Utilitas Math., Winnipeg, 1976, pp. 3–14. 17

1976

[6] [6]

Erdős, Some of my favourite unsolved problems, in: A

P. Erdős, Some of my favourite unsolved problems, in: A. Baker, B. Bollobás, A. Hajnal (Eds), A Tribute to Paul Erdős,Cambridge University Press, Cambridge, 1990, pp. 467–478

1990

[7] [7]

Erdős, Some of my favourite problems in various branches of combinatorics,Matematiche (Catania),47(1992), 231–240

P. Erdős, Some of my favourite problems in various branches of combinatorics,Matematiche (Catania),47(1992), 231–240

1992

[8] [8]

J. Gao, Q. Huo, C.-H. Liu, and J. Ma, A unified proof of conjectures on cycle lengths in graphs,Int. Math. Res. Not.2022(2022), no. 10, 7615–7653

2022