Graphs with girth $2\ell$ and without longer even holes are $3$-colorable

Rong chen

REVIEW 3 major objections 4 minor 1 cited by

Graphs with girth $2\ell$ and without longer even holes are $3$-colorable

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

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

Pith's one-line read For every ℓ≥5, graphs with girth 2ℓ and no induced even cycle longer than 2ℓ are 3-colorable.

desk verdict A serious and mostly well-organized proof of Wu–Xu–Xu's even-girth coloring conjecture for all ℓ ≥ 5, but the paper itself admits an error in the load-bearing Lemma 3.4 and never supplies the correction, so the main theorem is not yet fully established. read the letter →

arxiv 2509.01137 v1 pith:I3OECVKC submitted 2025-09-01 math.CO

Rong Chen This is my paper

classification math.CO MSC 05C1505C1705C69

keywords chromaticnumber3-colorabilitygirthevenholesK4-subdivisionthetagraphsshortjumpscutvertices

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 proves the even-hole analogue of a known coloring conjecture for all girth parameters ℓ≥5: every graph whose shortest cycle has length 2ℓ and that contains no induced even cycle longer than 2ℓ can be colored with three colors. The proof establishes a stronger structural statement — each such graph has either a vertex of degree two or a cut consisting of a single vertex or a single edge. Three-colorability then follows by taking a minimal counterexample and gluing colorings along the cut. The technical core is a classification of induced subgraphs built from the complete graph on four vertices (subdivisions of K4) and of certain 'jump' paths across an even hole. The result advances a conjecture that was previously open for even girth outside small cases.

What carries the argument

The load-bearing objects are induced theta graphs (two vertices joined by three internally disjoint paths), subdivisions of K4 classified by the parity of their face cycles as odd, even, or balanced, and 'jumps' over an even hole C: induced paths between nonadjacent vertices of C whose interiors avoid C. A short jump has interior anticomplete to C; a local jump across one vertex has interior attached only near a single vertex of C. Lemma 2.5 says that, in a graph with no degree-2 vertex and no K1/K2-cut, every 3-vertex path on C must be rescued by one of these jumps; Lemma 3.4 classifies the induced K4-subdivisions that arise from pairs of jumps; and the proof of Theorem 1.4 forces a 3-verte

What would settle it

Find a graph in H_5 — girth 10, no induced even cycle longer than 10 — with minimum degree at least 3 and no cut of one vertex or one edge; any such graph would refute Theorem 1.4 and reopen the coloring claim. More locally, an induced subgraph satisfying Lemma 3.4's hypotheses but none of its three conclusions would pinpoint the failure.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.4: for each integer ℓ≥5, every graph in H_ℓ — girth exactly 2ℓ and no induced even cycle of length at least 2ℓ+2 — has a degree-2 vertex or a K1/K2-cut. This implies Theorem 1.3, that every graph in H_ℓ is 3-colorable. The implication is short: a minimal non-3-colorable graph in H_ℓ must have minimum degree at least 3, so Theorem 1.4 supplies a one-vertex or one-edge cut; the two pieces are smaller, hence 3-colorable, and their colorings agree on the cut. The body of the proof rules out a counterexample to Theorem 1.4 by studying a shortest even hole C and the set S of endpoints of 'short jumps' over C, using parity of surrounding theta graphs and the c

Load-bearing premise

Lemma 3.4, a classification of certain induced subgraphs built from the complete graph on four vertices, is the load-bearing step; the acknowledgments say a reader found an error in an earlier version of that lemma, and the final contradiction of Theorem 1.4 depends on its corrected form.

Editorial extensions

If this is right

Conjecture 1.2 is true for every ℓ≥5: girth 2ℓ plus absence of longer even holes forces 3-colorability.
Every graph in H_ℓ, ℓ≥5, is cut-reducible: it contains a degree-2 vertex or a single-vertex/single-edge cut, so 3-colorings can be composed from smaller pieces.
The stronger Theorem 1.4 cannot hold for ℓ=2: complete bipartite graphs belong to H_2 and have no such cut, while still being 3-colorable.
The author states that the condition ℓ≥5 is used only in the final proof, so the same structural approach may extend to ℓ=4.

Reading between the lines

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

If the structural theorem is made constructive, it yields a natural recursive 3-coloring algorithm: find the cut or degree-2 vertex, color the two sides, and glue; the paper does not claim such an algorithm.
The degree-2/cut dichotomy suggests H_ℓ graphs are built from 3-connected 'atoms' each containing a long even hole; characterizing those atoms could reduce the coloring problem to a finite list for each ℓ.
The same parity-based jump machinery might transfer to the odd-girth family with girth 2ℓ+1, where the companion conjecture is now fully resolved, and yield a unified proof of both conjectures.
Because the final contradiction is sensitive to ℓ≥5, an independent re-verification of Lemma 3.4's classification is the natural first step toward pushing the theorem to ℓ=4.

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

The thing to know: this paper proves the even-girth analogue of Wu–Xu–Xu's coloring conjecture for all ℓ ≥ 5, and it does so with a substantial structural theorem. That is genuinely new—the odd-girth family was settled, but H_ℓ for ℓ ≥ 5 was open. The author adapts earlier odd-girth techniques to the even-girth setting with real skill, and the core structural result (Theorem 1.4: every such graph has a degree-2 vertex or a K1- or K2-cut) is exactly the kind of statement that gives 3-colorability by minimal counterexample. Lemmas 2.2, 3.3, 4.1–4.5 look like serious pieces of induced-cycle structure. The paper is also honest about scope: complete bipartite graphs kill any hope for ℓ = 2, and the author notes ℓ = 4 may be approachable with the same machinery. The writing is dense but organized, and the proof strategy is credible.

The soft spot is real and load-bearing. In the acknowledgments, the author thanks Zijian Deng for finding "an err in the proof of Lemma 3.4," but the manuscript never says whether the error was fixed or what the repair is. That matters because Lemma 3.4 is not peripheral. Lemma 4.3(2) depends on it, and Lemma 4.3 feeds Lemmas 4.4, 4.5, and the final contradiction in Theorem 1.4. So the central theorem currently rests on an unstated repair. The proof of Lemma 3.4 is a long case analysis with many "by symmetry" and "following a similar way" steps, which is typical for this subfield but makes independent verification hard. I did not find another fatal flaw; most of the argument is careful and internally consistent. But the unresolved status of Lemma 3.4 is a missing proof obligation, not a style complaint. The reader's conditional verdict is fair.

Minor comment: a few places, like the proof of Lemma 3.3's subclaim 3.3.2, compress reasoning with "following a similar way." That is acceptable in a manuscript under revision, but it adds to the verification burden.

Who is this for: anyone working on chromatic number, girth, and induced even cycles. It is a meaningful step on an open conjecture and deserves a serious referee. My recommendation: do not desk reject. Send to review, and ask the author to state explicitly how Lemma 3.4 was corrected and to rewrite its proof with fewer symmetry omissions. If the gap closes, this is a publishable result.

Referee Report

3 major / 4 minor

Summary. The paper addresses a conjecture of Wu, Xu, and Xu on 3-colorability of graphs of girth 2ℓ with no even hole longer than 2ℓ. The main theorem (Theorem 1.3) proves the conjecture for all ℓ ≥ 5. It is derived from a stronger structural result (Theorem 1.4): such graphs always have a vertex of degree 2 or a K1- or K2-cut. The proof is a lengthy structural case analysis: Section 2 develops tools on induced theta subgraphs and jumps over even holes, Section 3 classifies induced subdivisions of K4, and Section 4 uses these classifications to force a contradiction if a minimal counterexample exists. The author states in the acknowledgments that a colleague found an error in Lemma 3.4, but no correction is described.

Significance. If the proof is correct, this is a substantial advance: it proves the even-hole counterpart of the odd-girth conjecture for ℓ ≥ 5, and Theorem 1.4 is a strong structural statement. The argument is purely combinatorial and contains no fitted parameters, which is a strength. However, since the central structural classification (Lemma 3.4) is explicitly flagged as containing an error and no repair is given, the theorem is currently conditional. The paper is not suitable for publication until this lemma is corrected and the dependency chain is verified.

major comments (3)

[§5 and §3, Lemma 3.4] The acknowledgments say that Zijian Deng found 'an err in the proof of Lemma 3.4', but the manuscript does not state whether the error was corrected or how. Lemma 3.4 is load-bearing: in Lemma 4.3(2) the proof uses it directly ('So (2) holds from Lemma 3.4'), and Lemma 4.3 is used in Lemmas 4.4, 4.5, and in the final contradiction of Theorem 1.4. Without a corrected proof of Lemma 3.4, Theorem 1.4 is not established. Please provide the corrected argument, state whether the statement changes, and re-verify each downstream invocation.
[§3, Lemma 3.4 proof] The proof of Lemma 3.4 is too compressed for verification, even apart from the acknowledged error. For example, in Case 1 the proof assumes p1, p2, p3 > 1 'by symmetry' and then asserts a parity claim without detail; in Case 2, after a lengthy argument for p3 = 1, it says 'Similarly, p2 = 1'; in Case 3 it uses 'by symmetry and the claim proved in the last paragraph' to eliminate an alternative. Because this lemma is the classification on which Section 4 depends, these reductions need to be spelled out.
[§4, Lemma 4.4(1)] The proof of Lemma 4.4(1) contains another compressed step in the dependency chain. In the case where P1 ∪ P2 is not connected and |{x, y} ∩ N(C)| = 0, the proof says 'following a similar way as the last paragraph, we can prove the lemma'. This is a nontrivial case: the conclusion is a short jump between one of s1, s2 and one of the ends of the other jump. Lemma 4.4 is used in Lemma 4.5 and in the final proof of Theorem 1.4, so this step must be written out rather than left to analogy.

minor comments (4)

[Throughout] There are numerous typographical errors: 'Key W ords', 'P Qdenote', 'qdenote', 'the the', 'Whether are all graphs...', 'an err', and 'For a similar season' should be 'For a similar reason'. These do not affect the mathematics but should be fixed.
[Abstract] The abstract says 'no even hole with length greater than 2ℓ', while the introduction defines Hℓ by having no even holes of length at least 2ℓ+2. These are equivalent, but the wording should be consistent.
[§3, Lemma 3.4] In the text before Case 2, the sentence 'p maybe equal to 0' and the claim that the two graphs in Figure 2 are the same when p = 0 could be clarified. If p = 0 is allowed, it would help to state explicitly how the ears are labelled in the degenerate case.
[§4, Lemma 4.3(1)] In the proof of Lemma 4.3(1), the statement 'Since G[V(P2 ∪ P1(u, v1))]\E(C) is connected and has S as its set of degree-1 vertices' is not immediately clear because S includes u1, which may have degree 2 depending on the shape of P1 ∪ P2. A sentence explaining the degree-1 status of each vertex in S would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained and does not reduce its main theorem to its inputs or to a self-citation chain.

full rationale

This is a pure mathematics proof with no fitted parameters, free constants, or data-fitting steps, so the classic circularity patterns (self-definitional, fitted input called prediction) do not apply. The proof of Theorem 1.3 derives 3-colorability from the stronger structural Theorem 1.4 by a minimal-counterexample argument, and Theorem 1.4 is proved from lemmas developed inside the paper (Lemmas 2.1–2.6, 3.1–3.4, 4.1–4.5). The author's own prior work [2] is cited only as context for the analogous odd-hole conjecture and is not used as a load-bearing premise for the results here. No lemma is defined in terms of the target conclusion, and no equation-level reduction of the conclusion to an assumption occurs. The only substantive concern is the acknowledgment that Zijian Deng found an error in the proof of Lemma 3.4, with no corrected proof supplied in the manuscript. That is a proof gap or correctness risk, not circularity: Lemma 3.4 is a structural classification lemma, and there is no indication that its statement incorporates the theorem being proved or that its proof assumes 3-colorability. Accordingly, the circularity score is 0.

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

The paper introduces no free parameters, no new postulated entities, and no novel axioms. The proof is a standard structural argument; the only burden is the correctness of the lengthy case analysis.

assumptions (3)

standard math Standard definitions and basic facts of finite simple graphs, girth, holes, and colorings.
Used throughout; no specialized unproved results are needed for the main proof.
domain assumption Every graph in H_ℓ contains an even hole of length 2ℓ.
A shortest cycle (which has length 2ℓ by the girth condition) is chordless and hence an even hole. This is used at the start of the proof of Theorem 1.4.
standard math The Strong Perfect Graph Theorem and Scott-Seymour χ-boundedness results are cited for context only.
Mentioned in the introduction to frame the problem; the proof does not invoke them.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Graphs with girth $2\ell$ and without longer even holes are $3$-colorable." pith.science (2026). https://pith.science/paper/I3OECVKC

@misc{pith2026250901137,
  author       = {Pith},
  title        = {Pith review of: Graphs with girth $2\ell$ and without longer even holes are $3$-colorable},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I3OECVKC}},
  note         = {Machine review of arXiv:2509.01137}
}

abstract

For a number $\ell\geq 2$, let $\mathcal{H}_{\ell}$ denote the family of graphs which have girth $2\ell$ and have no even hole with length greater than $2\ell$. Wu, Xu, and Xu conjectured that every graph in $\bigcup_{\ell\geq2}\mathcal{H}_{\ell}$ is 3-colorable. In this paper, we prove that every graph in $\mathcal{H}_{\ell}$ is 3-colorable for any integer $\ell\geq5$.

Figures

Figures reproduced from arXiv: 2509.01137 by the authors.

**Figure 1.** u1, u2, u3, u4 are the degree-3 vertices of H. Let C1, C2, C3, C4 be the face cycles of H. Let a1, a2, b1, b2, d, q denote the lengths of ears A1, A2, B1, B2, D, Q, respectively. Set a := a1 + a2 and b := b1 + b2. Let H be an induced subgraph of a graph G that is isomorphic to a subdivision of K4. When all face cycles of H are odd, we say that H is an odd K4-subdivision; and when all face cycles of H are even, we sa… view at source ↗

**Figure 2.** Let C, C1, C2, C3, C4 be the face cycles of H. Set pi := |Pi | for any integer 1 ≤ i ≤ 4. Let a1, a2, a3, a4, p denote the lengths of its corresponding ears of H. For each 1 ≤ i ≤ 4, we have pi , ai ≥ 1. But p maybe equal to 0. Lemma 3.4. Let ℓ ≥ 4 be an integer and H be an induced subgraph of a graph G ∈ Hℓ . Assume that H is pictured as [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Graphs with girth 8 and without longer even holes are 3-colorable
math.CO 2026-05 unverdicted novelty 7.0 of 10

Every graph in the family H_4 is 3-colorable.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

Addario-Berry, M

L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, P. Seymour, Bisimplicial vertices in even-hole-free graphs, J. Combin. Theory Ser. B. 98 (2008), 1119-1164

work page 2008
[2]

Chen, Graphs with girth 2 ℓ + 1 and without longer odd holes are 3-colorable, J

R. Chen, Graphs with girth 2 ℓ + 1 and without longer odd holes are 3-colorable, J. Graph Theory. 108 (2025), 661-671

work page 2025
[3]

Chudnovsky, P

M. Chudnovsky, P. Seymour, Proof of a conjecture of Plummer and Zha, J. Graph Theory. 103 (2023), 437-450

work page 2023
[4]

Chudnovsky, P

M. Chudnovsky, P. Seymour, Even-hole-free graphs still have bisimplicial vertices, J. Comb. Theory Ser. B. 161 (2023), 331-381

work page 2023
[5]

Nelson, M

D. Nelson, M. Plummer, N. Robertson, X. Zha, On a conjecture concerning the Petersen graph. Electron. J. Combin. 18 (2011), #P20

work page 2011
[6]

Plummer, X

M. Plummer, X. Zha, On a conjecture concerning the Petersen Graph: Part II. Electron. J. Combin. 21 (2014), #P1.34

work page 2014
[7]

Scott and P

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. I. Odd holes, J. Comb. Theory Ser. B. 121 (2016), 68-84

work page 2016
[8]

Scott and P

A. Scott and P. Seymour, A survey of χ-boundedness, J. Graph Theory. 95 (2020), 473-504

work page 2020

Show all 12 references

[9]

Y. Wang, R. Wu, Graphs with girth 9 and without longer odd holes are 3-colorable, J. Graph Theory. 106 (2024), 871-886

2024
[10]

D. Wu, B. Xu, Y. Xu, On coloring of graphs of girth 2 ℓ + 1 without longer odd holes (in Chinese), Sci Sin Math. 52 (2022), 1-18

2022
[11]

D. Wu, B. Xu, Y. Xu, The chromatic number of heptagraphs, J. Graph Theory. 106 (2024), 711-736

2024
[12]

B. Xu, G. Yu, X. Zha, A note on chromatic number and induced odd cycles. Electron. J. Combin. 24 (2017), #P4.32. 20

2017

Pith tools

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

[1] [1]

Addario-Berry, M

L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, P. Seymour, Bisimplicial vertices in even-hole-free graphs, J. Combin. Theory Ser. B. 98 (2008), 1119-1164

work page 2008

[2] [2]

Chen, Graphs with girth 2 ℓ + 1 and without longer odd holes are 3-colorable, J

R. Chen, Graphs with girth 2 ℓ + 1 and without longer odd holes are 3-colorable, J. Graph Theory. 108 (2025), 661-671

work page 2025

[3] [3]

Chudnovsky, P

M. Chudnovsky, P. Seymour, Proof of a conjecture of Plummer and Zha, J. Graph Theory. 103 (2023), 437-450

work page 2023

[4] [4]

Chudnovsky, P

M. Chudnovsky, P. Seymour, Even-hole-free graphs still have bisimplicial vertices, J. Comb. Theory Ser. B. 161 (2023), 331-381

work page 2023

[5] [5]

Nelson, M

D. Nelson, M. Plummer, N. Robertson, X. Zha, On a conjecture concerning the Petersen graph. Electron. J. Combin. 18 (2011), #P20

work page 2011

[6] [6]

Plummer, X

M. Plummer, X. Zha, On a conjecture concerning the Petersen Graph: Part II. Electron. J. Combin. 21 (2014), #P1.34

work page 2014

[7] [7]

Scott and P

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. I. Odd holes, J. Comb. Theory Ser. B. 121 (2016), 68-84

work page 2016

[8] [8]

Scott and P

A. Scott and P. Seymour, A survey of χ-boundedness, J. Graph Theory. 95 (2020), 473-504

work page 2020