Pith. sign in

REVIEW 2 minor 19 references

Graphs with girth 8 and without longer even holes are 3-colorable

T0 review · 0 major / 2 minor · reviewed 2026-06-29 · grok-4.3

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

Pith's one-line read Every graph with girth 8 and no even hole longer than 8 is 3-colorable.

desk verdict This settles the ℓ=4 case of the Wu-Xu-Xu conjecture via induction on a minimal counterexample with exhaustive casework on 8-cycles. read the letter →

arxiv 2605.27943 v1 pith:UNA7PRDY submitted 2026-05-27 math.CO

Yan Wang , Rong Wu This is my paper
classification math.CO
keywords 3-colorablegirthevenholesH_4graphcoloringconjecture
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

The paper proves that all graphs in the family H_4 are 3-colorable. H_4 consists of graphs having girth 8 and containing no even hole longer than 8. This resolves the ℓ=4 case of the conjecture that graphs in H_ℓ are 3-colorable for all ℓ ≥ 2. Prior work covered ℓ ≥ 5, making this the next step toward confirming the full conjecture. Readers interested in graph coloring would care because these restrictions on cycles appear to force the chromatic number to be at most 3.

What carries the argument

The family H_4 of graphs with girth 8 and no even hole longer than 8, together with the case analysis establishing their 3-colorability.

What would settle it

A single graph with girth 8, no even hole longer than 8, and chromatic number four would disprove the claim.

Watch

Extended reading notes

Core claim

The authors prove that every graph in H_4 is 3-colorable, where H_4 denotes the family of graphs which have girth 8 and have no even hole of length greater than 8.

Load-bearing premise

The structural properties of graphs in H_4 permit a complete case analysis or induction that establishes 3-colorability without exceptions.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The paper proves that every graph in the family H_4—graphs with girth exactly 8 and no even hole longer than 8—is 3-colorable. This confirms the Wu-Xu-Xu conjecture for ℓ=4. The argument proceeds by induction on |V(G)|, considering a minimal counterexample G in H_4 and performing an exhaustive case analysis of reducible configurations around the possible 8-cycles, using the girth and hole-length restrictions to limit attachments and force either a coloring or a smaller counterexample.

Significance. The result fills the remaining case ℓ=4 after Chen's theorem for ℓ≥5, thereby establishing 3-colorability for the entire union over ℓ≥2. The induction-plus-reducibility method is standard for coloring problems on hole-restricted graphs; when the case analysis is complete it supplies a self-contained structural proof without external parameters or computational verification.

minor comments (2)
  1. The abstract states the result but does not indicate the proof technique; a single sentence on the induction approach would improve readability for readers familiar with the conjecture.
  2. Notation for the family H_ℓ and the even-hole condition is introduced clearly in the abstract and introduction, but a short table or diagram summarizing the forbidden substructures for ℓ=4 would aid quick reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the accurate summary of the result, and the recommendation to accept. We are pleased that the work completes the proof of the Wu-Xu-Xu conjecture for all ℓ ≥ 2.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; self-contained proof

full rationale

The paper establishes 3-colorability of graphs in H_4 via induction on |V(G)| for a minimal counterexample G, together with exhaustive analysis of reducible configurations around 8-cycles permitted by the girth-8 and no-longer-even-hole hypotheses. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-definition, or load-bearing self-citation whose justification is internal to the present manuscript. The cited prior results (Wu-Xu-Xu conjecture, Chen's theorem for ℓ≥5) are external and the central argument is a direct structural proof, not a renaming or ansatz smuggling.

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

No free parameters or invented entities are introduced; the paper proves a theorem using existing concepts.

assumptions (1)
  • standard math Basic properties of graphs, cycles, girth, and coloring
    The result relies on standard graph theoretic definitions and theorems.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graphs with girth 8 and without longer even holes are 3-colorable." pith.science (2026). https://pith.science/paper/UNA7PRDY

@misc{pith2026260527943,
  author       = {Pith},
  title        = {Pith review of: Graphs with girth 8 and without longer even holes are 3-colorable},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UNA7PRDY}},
  note         = {Machine review of arXiv:2605.27943}
}
abstract

For an integer $\ell\geq 2$, let ${\cal{H}}_{\ell}$ denote the family of graphs which have girth $2\ell$ and have no even hole of length greater than $2\ell$. Wu, Xu and Xu conjectured that every graph in $\bigcup_{\ell\geq 2} {\cal{H}}_{\ell}$ is $3$-colorable. Chen showed that every graph in $\bigcup_{\ell\geq 5} {\cal{H}}_{\ell}$ is $3$-colorable. In this paper, we prove that every graph in ${\cal{H}}_4$ is $3$-colorable.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 3 canonical work pages

  1. [1]

    Addario-Berry, M

    L. Addario-Berry, M. Chudnovsky, F. Havet, B.Reed and P. Seymour, Bisimplicial vertices in even-hole-free graphs, Journal of Combinatorial Theory, Series B,98(2008) 1119–1164

    2008

  2. [2]

    Chen, Graphs with girth 2ℓand without longer even holes are 3-colorable, arXiv preprint arXiv:2509.01137 (2025)

    R. Chen, Graphs with girth 2ℓand without longer even holes are 3-colorable, arXiv preprint arXiv:2509.01137 (2025)

    work page arXiv 2025

  3. [3]

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

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

    2025

  4. [4]

    Chudnovsky, N

    M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem, Annals of Mathematics,164(2006) 51-229

    2006

  5. [5]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour, Even-hole-free graphs still have bisimplicial vertex, Journal of Combinatorial Theory, Series B,161(2023) 331–381

    2023

  6. [6]

    Chudnovsky and P

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

    2023

  7. [7]

    L. Cook, J. Horsfield, M.Preissmann, C. Robin, P. Seymour, N.L.D. Sintiari, N. Trotignon and K. Vuskovi´ c, Graphs with all holes the same length, Journal of Combinatorial Theory, Series B,168 (2024) 96–158

    2024

  8. [8]

    Gy´ arf´ as, On Ramsey covering-numbers, Colloquia Mathematic Societatis J´ anos Bolyai 10, Infinite and Finite Sets

    A. Gy´ arf´ as, On Ramsey covering-numbers, Colloquia Mathematic Societatis J´ anos Bolyai 10, Infinite and Finite Sets. North-Holland/American Elsevier, New York (1975) 801–816

    1975

Show all 19 references
  1. [9]

    C. T. Ho` ang and C. McDiarmid, On the divisibility of graphs, Discrete Mathematics,242(2002) 145–156

    2002

  2. [10]

    Nelson, M

    D. Nelson, M. Plummer, N. Robertson and X. Zha, On a conjecture concerning the Petersen graph, The Electronic Journal of Combinatorics,18(2011) P20, 37pp

    2011

  3. [11]

    Plummer and X

    M. Plummer and X. Zha, On a conjecture concerning the Petersen graph: Part II, The Electronic Journal of Combinatorics,21(2014) P1.34, 9pp

    2014

  4. [12]

    Sivaraman, Some problems on induced subgraphs, Discrete Applied Mathematics,236(2018) 422–427

    V. Sivaraman, Some problems on induced subgraphs, Discrete Applied Mathematics,236(2018) 422–427

    2018

  5. [13]

    A. D. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. I. odd holes, Journal of Combinatorial Theory, Series B,121(2016) 68–84

    2016

  6. [14]

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

    2020

  7. [15]

    Wang and R

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

    2024

  8. [16]

    Wang and R

    Y. Wang and R. Wu, Optimalχ-boundness ofℓ-holed graphs, arXiv: 2508.07034

  9. [17]

    D. Wu, B. Xu and Y. Xu, On coloring of graphs of girth 2l+ 1 without longer odd holes s (in Chinese), to appear in Science China: Mathematics http://doi.org/10.1360/SCM-2021-0373. See arXiv:2204.06284

    2021 doi

  10. [18]

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

    2024

  11. [19]

    B. Xu, G. Yu and X. Zha, A note on chromatic number and induced odd cycles, The Electronic Journal of Combinatorics,24(4) (2017) P4.32. 14

    2017

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.