Optimal coloring of $\{\mathrm{cap},\mathrm{even\ hole}\}$-free graphs with no short odd holes

Feng Liu; Shuang Sun; Yan Wang

REVIEW 1 major objections 3 minor 23 references

The exact coloring bound for {cap, even hole}-free graphs with no short odd holes is ceil((2q+1)/(2q)ω(G)), and it is attained.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

For every q≥3, every {cap, even hole}-free graph with no odd hole of length at most 2q−1 satisfies χ(G)≤ceil((2q+1)/(2q)ω(G)), and this bound is tight.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection Answers Chen–Xu–Xu's open problem with a sharp χ-binding bound for all q≥3; the proof mostly works, but Lemma 3.2 has a fixable gap where two partial colorings are glued on a shared bag without justification. the 1 major comments →

arxiv 2607.25396 v1 pith:WQTG7USV submitted 2026-07-28 math.CO

Optimal coloring of $\{\mathrm{cap},\mathrm{even\ hole}\}$-free graphs with no short odd holes

Feng Liu , Shuang Sun , Yan Wang This is my paper

classification math.CO MSC 05C1505C75

keywords chromatic numberclique numberchi-boundednesseven-hole-free graphscap-free graphsgood ear decompositionclique blowupodd holes

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

Resolving a question left open by prior work, the paper establishes the exact χ-binding function for {cap, even hole}-free graphs in which every odd hole has length at least 2q+1: the chromatic number is at most ceil((2q+1)/(2q)ω(G)). This coefficient 1+1/(2q) is shown to be necessary, since uniform clique blowups of the cycle C_{2q+1} achieve the bound. The proof works by showing that a minimal counterexample must be a nonempty clique blowup of a triangle-free graph admitting a good ear decomposition whose base is an odd hole, and then pushing the coloring through the final ear via two extension lemmas. The result generalizes earlier bounds of 5/4 and 7/6 times ω(G) and confirms the optimality of the whole family of coefficients for every q≥3.

Core claim

On its own terms, the theorem says: for every integer q≥3, if G contains no cap, no even hole, and no odd hole of length at most 2q−1, then χ(G) ≤ ceil((2q+1)/(2q)ω(G)) — and this is best possible. The proof reduces a minimal counterexample to a nonempty clique blowup of a triangle-free graph F with a good ear decomposition whose base graph is an odd hole. The critical step is to extend a given coloring of the bags along the last ear, using one lemma for a clique blowup of a path and another for a clique blowup of two odd holes intersecting in an edge. Sharpness is demonstrated by the uniform p-clique blowup of C_{2q+1}, which is cap-free, even-hole-free, has no short odd holes, and attains

What carries the argument

The central machinery is the reduction of the graph to a nonempty clique blowup of a triangle-free graph F (Corollary 2.4); a clique blowup replaces each vertex of F by a nonempty clique, with edges between bags exactly where F has edges. F is shown to admit a good ear decomposition (a sequential addition of induced paths with controlled neighbor counts) whose base is an odd hole. The two workhorse lemmas — Lemma 3.1 for a path-like blowup and Lemma 3.2 for two odd holes glued along an edge — prescribe how to choose color sets on the bags so that a precoloring of the initial bags extends to a proper coloring of the entire last-ear subgraph.

Load-bearing premise

The proof rests on a structural theorem stating that every connected cap-free, even-hole-free graph that cannot be split by a small separating clique and has no universal vertex is obtained from a triangle-free graph by blowing up each vertex into a clique; if this theorem carries a hidden extra condition, the reduction to a good ear decomposition never gets started.

What would settle it

A concrete counterexample would be, for some q≥3, a graph G that contains no cap, no even hole, and no odd hole of length at most 2q−1 but satisfies χ(G) > ceil((2q+1)/(2q)ω(G)); for instance, for q=3 this means a cap-free, even-hole-free graph with no 5-holes whose chromatic number exceeds ceil(7ω(G)/6).

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

Settles the open problem of whether the coefficient (2q+1)/(2q) is the optimal χ-binding function for these graphs, for every integer q≥3.
Shows that for this graph class the chromatic number is controlled exactly by the clique number, with an additive slack that shrinks to 0 as q grows.
Unifies earlier results: the cases q=2 and q=3 recover the known 5/4 and 7/6 upper bounds.
Provides an explicit extremal family — uniform clique blowups of C_{2q+1} — proving sharpness for every q.
Yields a structural description of minimal counterexamples as clique blowups of triangle-free graphs with good ear decompositions, excluding more complicated obstruction patterns.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The paper proves the bound but does not characterize equality cases; a natural next step is to investigate whether every graph attaining the bound must be a clique blowup of C_{2q+1} (or a minor variant).
The last-ear extension technique may transfer to neighboring classes, such as graphs that forbid caps and short odd holes but allow some even holes; this would be an editorial extension, not a claim of the paper.
The sharpness construction suggests that the extremal ratio is tied to the length of the shortest allowed odd hole, so changing the gap parameter 2q+1 may shift the optimal coefficient accordingly.

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.

Desk Editor's Note

Answers Chen–Xu–Xu's open problem with a sharp χ-binding bound for all q≥3; the proof mostly works, but Lemma 3.2 has a fixable gap where two partial colorings are glued on a shared bag without justification.

read the letter

This paper settles a natural problem in the χ-boundedness program: for every integer q≥3, every {cap, even hole}-free graph with no odd hole of length at most 2q−1 satisfies χ ≤ ceil((2q+1)/(2q) ω), and the bound is sharp. The q=3 case was already known; the upper bounds for q≥4 and the sharpness examples for all q≥3 are new. That is a real extension, not a repackaging.

The overall architecture is sound. The reduction to a minimal counterexample, the clique-cutset argument, and Corollary 2.4 (reducing to a nonempty clique blowup of a triangle-free graph with a good ear decomposition) all follow established lines. The last-ear argument is the core, and the two extension lemmas for path-like clique blowups are the meat. Lemma 3.1 is long but the counting arguments check out. The sharpness construction via uniform clique blowups of C_{2q+1} is clean and appears correct.

The soft spots are exactly where the stress-test points. Lemma 3.2 is incomplete as written. Lemma 3.1 is applied twice, once along each odd hole, and each application guarantees a coloring of that path with the bag Z using color set B. But nothing in the lemma guarantees that the two colorings assign the same colors to the individual vertices of Z. The sentence 'the two colorings together give a k-coloring of H' requires that agreement, and it is not proven. This is load-bearing: H is the union of the two paths glued along Y and Z, and a mismatch on Z would be a conflict on that clique. The gap is likely repairable — Z is a clique, and its neighbors have color sets disjoint from B, so one can permute the colors on Z within B to match one side — but that argument is not in the manuscript. Also, the set-selection in Claim 1 of Lemma 3.2 can be impossible as described, though a valid choice exists; that is a smaller editorial issue.

I do not see a deeper flaw. The reliance on Lemma 2.1 from [3] is not circularity; it is an independent published structural theorem. The paper does not pretend to new machinery; it is a substantial extension within a known program, and it resolves the problem it claims to resolve.

Bottom line: this deserves refereeing. The gaps in Lemma 3.2 are localized and fixable, and the result is important enough to warrant referee time. I would take a look at the revision after the standard 'rewrite Lemma 3.2' request. I would bring it to a reading group and would cite it in my own work.

Referee Report

1 major / 3 minor

Summary. The paper proves Theorem 1.3: for every integer q ≥ 3, every {cap, even hole}-free graph G with no odd hole of length at most 2q−1 satisfies χ(G) ≤ ceil((2q+1)/(2q) ω(G)), and this bound is sharp via uniform clique blowups of C_{2q+1}. This answers Problem 1.2 of Chen–Xu–Xu. The proof reduces a minimal counterexample to a nonempty clique blowup of a triangle-free graph using a structural theorem of Cameron–da Silva–Huang–Vušković, then uses a good ear decomposition due to Conforti–Cornuéjols–Kapoor–Vušković. The last ear is handled by two coloring-extension lemmas (Lemmas 3.1 and 3.2), and the sharpness construction is explicit.

Significance. If correct, the paper resolves a natural open problem and gives the optimal χ-binding function for the family of {cap, even hole}-free graphs with excluded short odd holes. The proof has a clean architecture: it converts a coloring problem into a structural statement about triangle-free graphs with good ear decompositions, and the sharpness example is simple and convincing. The paper also gives credit to the earlier structural results on which the proof relies. The main theorem, modulo the gap discussed below, is coherent and the sharpness construction is independently verifiable.

major comments (1)

[Lemma 3.2, final paragraph] The proof applies Lemma 3.1 twice, prescribing only the color set B on the shared bag Z. Lemma 3.1 guarantees a coloring in which V_r uses the color set B, but it does not prescribe a bijection between the vertices of V_r and B. Therefore the two extensions may assign different colors to the same vertex of Z, and the sentence 'the two colorings together give a k-coloring of H' is not justified as written. This is load-bearing because Z is the only common part of the two paths apart from Y∪X0∪X'_0, and the two paths are otherwise anticomplete. The gap is repairable: since Z is a clique, the colors used on Z in both colorings form the set B, and all neighbors of Z in H (namely Y, X_{2ℓ−2}, X'_{2t−2}) have color sets disjoint from B, so one may permute the colors on Z in the second extension to agree with the first without creating conflicts. This argument should be added explicitly before

minor comments (3)

[Introduction, §1] In the paragraph on 4-holed graphs, 'χ(G)≤ω (G)2' and 'χ(G)≤ 2ω(G)2' should read 'ω(G)^2' and '2ω(G)^2'.
[Throughout] There are several typographical/spacing issues: 'A capis' in the abstract, 'Let q≥ 3be an integer' in Theorem 1.3, and similar missing spaces. These do not affect the mathematics.
[Section 4, sharpness] The argument that an induced cycle in C^p_{2q+1} contains at most one vertex per bag is correct, but the phrase 'being true twins, would create a chord' deserves a short expansion: if two twins were consecutive on the cycle, the predecessor of one is adjacent to the other, producing a chord; if they were not consecutive, a similar chord appears. This is clear but could be stated more fully.

Circularity Check

0 steps flagged

No circularity: Theorem 1.3 is derived from independent external structure theorems, not from its own conclusion.

full rationale

The proof of Theorem 1.3 is a genuine derivation. It reduces a minimal counterexample to a clique blowup of a triangle-free graph via Corollary 2.4, which imports Lemma 2.1 ([3]) and Lemma 2.2 ([10]). Both are earlier published structural results independent of the present paper and of the target bound; neither is a restatement of Theorem 1.3. The d=0 base case and the sharpness construction use Lemma 2.3 ([4]), an external theorem giving the same extremal bound for clique blowups of odd cycles; using a previously proved special case is not circular. Lemma 3.1 and Lemma 3.2 are proven within the paper from the clique constraints and the arithmetic of color sets; they do not assume the target theorem. The sharpness example is shown to satisfy the hypotheses by a direct cap-free/even-hole-free argument and its chromatic number is computed from Lemma 2.3. There is no fitted parameter renamed as a prediction and no load-bearing self-citation: the author list (Liu, Sun, Wang) does not overlap with references [3], [4], [5], [10] that carry the structural load. An apparent reviewer concern that Lemma 3.2 does not explicitly force the two applications of Lemma 3.1 to agree on the shared bag Z is a proof-completeness issue, not circularity: it concerns whether the extension lemma is fully justified, not whether the conclusion is assumed as an input. Therefore the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No free parameters or invented entities. The paper's contribution is a derivation from existing structural theorems; the only novel objects are technical color-set constructions inside the lemmas.

axioms (5)

domain assumption Structural decomposition for {cap, 4-hole}-free graphs (Lemma 2.1, [3])
Imported from Cameron–da Silva–Huang–Vušković; it is the backbone of Corollary 2.4 and is not proved in this paper.
domain assumption Good ear decomposition theorem for odd-signable triangle-free graphs (Lemma 2.2, [10])
Used to guarantee the last ear used in Section 4; not proved here.
domain assumption Chromatic bound for clique blowups of odd cycles (Lemma 2.3, [4])
Used for the d=0 case and for sharpness; imported from Chen–Xu.
standard math Chordal graphs are perfect (Dirac [12])
Used to rule out hole-free counterexamples.
standard math Odd-signable via weight-one assignment for {triangle, even hole}-free graphs
Every induced cycle is odd, so assigning weight 1 works; used in Corollary 2.4.

reviewed 2026-08-01 · how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal coloring of $\{\mathrm{cap},\mathrm{even\ hole}\}$-free graphs with no short odd holes." pith.science (2026). https://pith.science/paper/WQTG7USV

@misc{pith2026260725396,
  author       = {Pith},
  title        = {Pith review of: Optimal coloring of $\\mathrmcap,\mathrmeven\ hole\$-free graphs with no short odd holes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WQTG7USV}},
  note         = {Machine review of arXiv:2607.25396}
}

Share X Bluesky LinkedIn Reddit HN

abstract

A \emph{hole} is an induced cycle of length at least four, and an \emph{even hole} is a hole of even length. A \emph{cap} is obtained from a hole by adding a vertex adjacent to exactly two consecutive vertices of the hole. Chen, Xu, and Xu proved that every $\{\mathrm{cap},\mathrm{even\ hole}\}$-free graph $G$ satisfies $\chi(G)\leq \left\lceil\frac{5}{4}\omega(G)\right\rceil$, and improved this bound to $\chi(G)\leq \left\lceil\frac{7}{6}\omega(G)\right\rceil$ when $5$-holes are also excluded. They asked whether, for every integer $q\geq3$, every $\{\mathrm{cap},\mathrm{even\ hole}\}$-free graph $G$ with no odd hole of length at most $2q-1$ satisfies $$ \chi(G)\leq \left\lceil\frac{2q+1}{2q}\omega(G)\right\rceil. $$ We answer this question affirmatively and show that the bound is sharp for every $q\geq3$.

Figures

Figures reproduced from arXiv: 2607.25396 by Feng Liu, Shuang Sun, Yan Wang.

**Figure 1.** Figure 1: From left to right: pan, diamond and cap. Chen, Xu, and Xu [5] proposed the following problem. Problem 1.2 (Chen–Xu–Xu [5]). Let q ≥ 3 be an integer. Does every {cap, even hole}-free graph G with no odd hole of length at most 2q − 1 satisfy χ(G) ≤ 2q + 1 2q ω(G) ? In this paper, we answer Problem 1.2 affirmatively. Theorem 1.3. Let q ≥ 3 be an integer. If G is a {cap, even hole}-free graph with no odd … view at source ↗

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 3 linked inside Pith

[1]

J. A. Bondy and U. S. R. Murty,Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008

2008
[2]

Cameron, S

K. Cameron, S. Chaplick and C. T. Hoàng, On the structure of (pan, even hole)-free graphs,J. Graph Theory87(2018), 108–129

2018
[3]

Cameron, M

K. Cameron, M. V. G. da Silva, S. Huang and K. Vušković, Structure and algorithms for (cap, even hole)-free graphs,Discrete Math.341(2018), 463–473

2018
[4]

Chen and B

R. Chen and B. Xu, Nearly optimal coloring of someC4-free graphs,arXiv:2409.06944 (2024)

Pith/arXiv arXiv 2024
[5]

R. Chen, B. Xu and Y. Xu, The optimal binding function for(cap,even hole )-free graphs, arXiv:2506.19580(2025)

Pith/arXiv arXiv 2025
[6]

Chudnovsky, N

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem,Ann. of Math.164(2006), 51–229

2006
[7]

Chudnovsky, A

M. Chudnovsky, A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. III. Long holes,Combinatorica37(2017), no. 6, 1057–1072

2017
[8]

Chudnovsky, A

M. Chudnovsky, A. Scott, P. Seymour and S. Spirkl, Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes,J. Combin. Theory Ser. B140(2020), 84–97

2020
[9]

Chudnovsky and P

M. Chudnovsky and P. Seymour, Even-hole-free graphs still have bisimplicial vertices,J. Combin. Theory Ser. B161(2023), 331–381

2023
[10]

Conforti, G

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Triangle-free graphs that are signable without even holes,J. Graph Theory34(2000), no. 3, 204–220

2000
[11]

L. Cook, J. Horsfield, M. Preissmann, C. Robin, P. Seymour, N. L. D. Sintiari, N. Trotignon, and K. Vušković, Graphs with all holes the same length,J. Combin. Theory Ser. B168(2024), 96–158

2024
[12]

G. A. Dirac, On rigid circuit graphs,Abh. Math. Sem. Univ. Hamburg25(1961), 71–76

1961
[13]

Gyárfás, On Ramsey covering-numbers,Infinite and Finite Sets2(1975), 801–816

A. Gyárfás, On Ramsey covering-numbers,Infinite and Finite Sets2(1975), 801–816

1975
[14]

Gyárfás, Problems from the world surrounding perfect graphs,Zastos

A. Gyárfás, Problems from the world surrounding perfect graphs,Zastos. Mat.19(1987), 413–441

1987
[15]

Huang, Y

S. Huang, Y. Zhou and Y. Chang, The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths,arXiv:2602.04403(2026)

arXiv 2026
[16]

Karthick and F

T. Karthick and F. Maffray, Square-free graphs with no six-vertex induced path,SIAM J. Discrete Math.33(2019), 874–909

2019
[17]

Kloks, H

T. Kloks, H. Müller and K. Vušković, Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences,J. Combin. Theory Ser. B99(2009), 733–800

2009
[18]

Scott and P

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. I. Odd holes,J. Combin. Theory Ser. B121(2016), 68–84. 10

2016
[19]

Scott and P

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

2020
[20]

Sivaraman, Some problems on induced subgraphs,Discrete Appl

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

2018
[21]

Vušković, Even-hole-free graphs: A survey,Appl

K. Vušković, Even-hole-free graphs: A survey,Appl. Anal. Discrete Math.4(2010), 219–240

2010
[22]

Wang and R

Y. Wang and R. Wu, Optimalχ-boundedness ofℓ-holed graphs,arXiv:2508.07034(2025)

Pith/arXiv arXiv 2025
[23]

D. B. West,Introduction to Graph Theory, Prentice Hall, 1996. 11

1996

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.

[1] [1]

J. A. Bondy and U. S. R. Murty,Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008

2008

[2] [2]

Cameron, S

K. Cameron, S. Chaplick and C. T. Hoàng, On the structure of (pan, even hole)-free graphs,J. Graph Theory87(2018), 108–129

2018

[3] [3]

Cameron, M

K. Cameron, M. V. G. da Silva, S. Huang and K. Vušković, Structure and algorithms for (cap, even hole)-free graphs,Discrete Math.341(2018), 463–473

2018

[4] [4]

Chen and B

R. Chen and B. Xu, Nearly optimal coloring of someC4-free graphs,arXiv:2409.06944 (2024)

Pith/arXiv arXiv 2024

[5] [5]

R. Chen, B. Xu and Y. Xu, The optimal binding function for(cap,even hole )-free graphs, arXiv:2506.19580(2025)

Pith/arXiv arXiv 2025

[6] [6]

Chudnovsky, N

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem,Ann. of Math.164(2006), 51–229

2006

[7] [7]

Chudnovsky, A

M. Chudnovsky, A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. III. Long holes,Combinatorica37(2017), no. 6, 1057–1072

2017

[8] [8]

Chudnovsky, A

M. Chudnovsky, A. Scott, P. Seymour and S. Spirkl, Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes,J. Combin. Theory Ser. B140(2020), 84–97

2020

[9] [9]

Chudnovsky and P

M. Chudnovsky and P. Seymour, Even-hole-free graphs still have bisimplicial vertices,J. Combin. Theory Ser. B161(2023), 331–381

2023

[10] [10]

Conforti, G

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Triangle-free graphs that are signable without even holes,J. Graph Theory34(2000), no. 3, 204–220

2000

[11] [11]

L. Cook, J. Horsfield, M. Preissmann, C. Robin, P. Seymour, N. L. D. Sintiari, N. Trotignon, and K. Vušković, Graphs with all holes the same length,J. Combin. Theory Ser. B168(2024), 96–158

2024

[12] [12]

G. A. Dirac, On rigid circuit graphs,Abh. Math. Sem. Univ. Hamburg25(1961), 71–76

1961

[13] [13]

Gyárfás, On Ramsey covering-numbers,Infinite and Finite Sets2(1975), 801–816

A. Gyárfás, On Ramsey covering-numbers,Infinite and Finite Sets2(1975), 801–816

1975

[14] [14]

Gyárfás, Problems from the world surrounding perfect graphs,Zastos

A. Gyárfás, Problems from the world surrounding perfect graphs,Zastos. Mat.19(1987), 413–441

1987

[15] [15]

Huang, Y

S. Huang, Y. Zhou and Y. Chang, The optimal chromatic bound for even-hole-free graphs without induced seven-vertex paths,arXiv:2602.04403(2026)

arXiv 2026

[16] [16]

Karthick and F

T. Karthick and F. Maffray, Square-free graphs with no six-vertex induced path,SIAM J. Discrete Math.33(2019), 874–909

2019

[17] [17]

Kloks, H

T. Kloks, H. Müller and K. Vušković, Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences,J. Combin. Theory Ser. B99(2009), 733–800

2009

[18] [18]

Scott and P

A. Scott and P. Seymour, Induced subgraphs of graphs with large chromatic number. I. Odd holes,J. Combin. Theory Ser. B121(2016), 68–84. 10

2016

[19] [19]

Scott and P

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

2020

[20] [20]

Sivaraman, Some problems on induced subgraphs,Discrete Appl

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

2018

[21] [21]

Vušković, Even-hole-free graphs: A survey,Appl

K. Vušković, Even-hole-free graphs: A survey,Appl. Anal. Discrete Math.4(2010), 219–240

2010

[22] [22]

Wang and R

Y. Wang and R. Wu, Optimalχ-boundedness ofℓ-holed graphs,arXiv:2508.07034(2025)

Pith/arXiv arXiv 2025

[23] [23]

D. B. West,Introduction to Graph Theory, Prentice Hall, 1996. 11

1996

Optimal coloring of $\{\mathrm{cap},\mathrm{even\ hole}\}$-free graphs with no short odd holes

The reading

Core claim §

What carries the argument

Load-bearing premise §

What would settle it §

If this is right

Where Pith is reading between the lines

discussion (0)

Core claim

Load-bearing premise

What would settle it