Optimal binding function for (cap,even hole)-free graphs with no short odd holes

Chenglong Deng; Xuding Zhu

REVIEW 2 major objections 3 minor 19 references

The paper proves that every (cap, even hole)-free graph G with no induced odd cycle of length at most 2q−1 has chromatic number at most ⌈(2q+1)/(2q)ω(G)⌉ for every q≥3, confirming the conjectured optimal binding function.

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 ↗

The authors attempt to confirm the optimal binding function conjecture for (cap, even hole)-free graphs with no short odd holes, extending known cases q≤3 to all q≥3, but the proof contains a concrete error in the odd-cycle base case.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection The main theorem is plausible and the structural reduction is elegant, but the base-case coloring in Lemma 2.4 is demonstrably false, so the proof does not stand as written. the 2 major comments →

arxiv 2607.27850 v1 pith:I2M4P6VX submitted 2026-07-30 math.CO

Optimal binding function for (cap,even hole)-free graphs with no short odd holes

Chenglong Deng , Xuding Zhu This is my paper

classification math.CO MSC 05C1505C1705C38

keywords chromatic numberχ-boundednessbinding functioneven-hole-free graphscap-free graphsodd holesweighted coloringear decomposition

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

The paper settles a conjecture about how expensive it is to forbid short odd holes in graphs that are already free of induced even cycles and of caps (a hole with an extra vertex attached to two consecutive hole vertices). The claim: for every integer q≥3, such a graph G has chromatic number at most (2q+1)/(2q) times its clique number, rounded up. This is the best possible constant, because blow-ups of a (2q+1)-cycle by cliques need exactly that many colors. The proof reduces the problem to a weighted coloring lemma on the triangle-free skeleton of G and extends the previously known range q≤3 to all q. A corollary gives the same constant as a bound on the fractional chromatic number, and the result is one of the rare exact chromatic bounds known for a hereditary χ-bounded family.

Core claim

The central claim is Theorem 1.1: if G is a (cap, even hole)-free graph with no odd hole of length at most 2q−1 for some q≥3, then χ(G) ≤ ⌈(2q+1)/(2q)ω(G)⌉. The bound is sharp: the lexicographic product C_{2q+1}[K_k], where each vertex of the odd cycle is replaced by a k-clique, has clique number 2k and needs ⌈(2q+1)k/2⌉ colors. The proof is organized around Lemma 2.4, a weighted-coloring statement: taking the triangle-free skeleton F obtained by contracting the cliques of G, with weights w(v) equal to the clique sizes, a K-coloring exists for K = ⌈(2q+1)/(2q)W⌉, where W is the maximum weight of an edge. Since F is triangle-free and even-hole-free, it can be built from a hole by adding good

What carries the argument

The carrying object is the weighted skeleton F of G: a maximal triangle-free induced subgraph with no clique cutset, obtained by reversing the clique blow-up; each skeleton vertex carries weight w(v), the size of the clique it represents. Lemma 2.4 is the workhorse: it states that F has a K-coloring — an assignment of w(v)-element subsets of [K] to each vertex, disjoint along edges — with K = ⌈(2q+1)/(2q)W⌉. The proof leans on two structural facts: an ear-decomposition theorem saying every such triangle-free even-hole-free graph without clique cutsets is built from a hole by repeated good ear additions (a path inserted between two consecutive neighbors of a vertex, with parity and wheel cond

Load-bearing premise

The load-bearing premise is that the minimal-counterexample induction in Lemma 2.4 goes through: after deleting the internal vertices B of an ear, the smaller graph F−B is assumed to satisfy the same hypotheses, in particular having no clique cutset, but this inheritance is not proved; the displayed coloring for the odd-cycle base case also fails to be proper in general (for C7 with unit weights and K=3, both endpoints of an edge receive color 1).

What would settle it

Compute the proposed base-case coloring of Lemma 2.4 for the 7-cycle with all weights equal to 1 and K=3: the construction assigns color 1 to both adjacent vertices v0 and v6, so it is not a proper 3-coloring. That calculation falsifies the base case as stated; to test the theorem itself, one would search for a (cap, even hole)-free graph with no odd hole of length ≤5 and chromatic number exceeding ⌈7ω/6⌉.

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

If this is right

The conjecture is now fully settled: the q≤3 cases were known, and this paper proves q≥3, so every integer q≥2 is covered.
For these graphs, the fractional chromatic number is bounded by (2q+1)/(2q)ω(G), which follows from applying the theorem to a lexicographic product with K_{2q}.
The constant (2q+1)/(2q) cannot be improved within the family, since C_{2q+1} blow-ups attain it exactly.
The earlier 5/4 and 7/6 chromatic bounds for (cap, even hole)-free graphs and their 5-hole-free subclass appear as the q=2 and q=3 instances.

Where Pith is reading between the lines

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

A natural repair of the proof is to strengthen Lemma 2.4's induction hypothesis so that it tolerates clique cutsets in the ear-deleted graph F−B, or to prove directly that F−B inherits the no-clique-cutset property.
The path-coloring lemma (Lemma 2.5) is self-contained and can be extracted as a standalone tool for weighted list-coloring of even-length paths with specified endpoint color sets.
The extremal examples suggest a full structure theorem for graphs meeting the bound: every tight example may be a clique blow-up of a (2q+1)-cycle; the paper does not address this.
The same skeleton-and-ears scheme could be tried with other forbidden induced cycles to produce exact constants for related χ-bounded families.

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

The main theorem is plausible and the structural reduction is elegant, but the base-case coloring in Lemma 2.4 is demonstrably false, so the proof does not stand as written.

read the letter

Quick take: this is a serious attempt at a very nice result, but the proof as written doesn't go through. The concrete coloring mistake in the odd-cycle base case of Lemma 2.4 isn't a gap in the exposition—the displayed formula just doesn't produce disjoint colors for adjacent vertices.

What's genuinely good: the target theorem—confirming Chen–Xu–Xu for all q≥3—is a substantial, natural next step after [4], and the reduction of Theorem 1.1 to a weighted list-coloring lemma (Lemma 2.4) is clean, following the established minimal-counterexample + ear-decomposition strategy. If the lemma were true, the blow-up argument and the fractional chromatic number corollary would be straightforward and correct. The paper credits the prior structural work (Conforti et al., Cameron et al.) properly and doesn't try to hide the dependence.

The problem: Lemma 2.4's induction starts on odd cycles, and the interval assignment is wrong. The stress-test example is correct: q=3, r=3, W=6, K=7, weights 5,1,5,1,5,1,1 on C7. The construction gives φ(v0) containing 5 and φ(v6)={5}, while v0v6 is an edge. So the claim that φ(vi)∩φ(v_{i+1})=∅ for all i is false. Since this is the base case of the induction, the proof of Lemma 2.4 collapses; you can't wave it away by saying the theorem might be true. The secondary point about F⁻=F−B not inheriting the no-clique-cut condition is also real: the minimality step silently assumes that property, and without an argument the induction can't be applied. That's a smaller but genuine hole.

One more thing worth checking if anyone picks up a revision: the proof of Lemma 2.5 is very dense and the induction step doesn't fully justify why the chosen A_{2m-2} satisfies the intersection bound; I'd want that written out. But I haven't found a concrete counterexample there.

Net: I don't think the manuscript in this form can be accepted. The main idea and the structural reduction deserve a serious referee, and the flaws look repairable—the interval coloring could likely be fixed by a more careful choice of starting points. But as submitted, the central lemma is unproven, and the base case is demonstrably false. I'd send it to review anyway, because the target result is important and the approach is close enough that a careful referee could help the authors fix it.

Referee Report

2 major / 3 minor

Summary. The paper aims to prove the Chen-Xu-Xu conjecture for (cap, even hole)-free graphs with no odd hole of length at most 2q−1, for every q≥3: the chromatic number is at most ceil((2q+1)/(2q)ω(G)). The proof reduces the problem to a weighted coloring lemma (Lemma 2.4) for the triangle-free even-hole-free skeleton F with no clique cutset and no short odd holes. Lemma 2.4 is proved by induction on |V(F)|. The odd-cycle base case is treated by an explicit interval coloring, and the induction step uses Conforti et al.'s good-ear decomposition, removes the internal vertices B of two ear segments, applies the induction hypothesis to F^-=F−B, and extends the resulting coloring by a path-precoloring lemma. The paper also derives a fractional chromatic number bound as a corollary.

Significance. If the proof were correct, it would settle the full conjecture of Chen, Xu, and Xu and give the optimal binding function for this family, with the sharpness already witnessed by lexicographic products C_{2q+1}[K_k]. The reduction from the graph coloring problem to a weighted coloring lemma for the skeleton is natural, and the use of the existing structural theorems of Conforti et al. and Cameron et al. is appropriate; there is no circularity. The paper does not contain machine-checked proofs or reproducible code; the argument is a conventional structural induction. However, the proof of the central engine, Lemma 2.4, has a concrete false statement in its base case and a second unproved induction hypothesis. These are not presentation issues: they invalidate the proof of Theorem 1.1 as written.

major comments (2)

[Lemma 2.4, odd-cycle base case] The displayed interval coloring is false. Take q=3, r=3, W=6, K=7, and assign w(v0)=w(v2)=w(v4)=5, w(v1)=w(v3)=w(v5)=1, w(v6)=1. Then w(v6)≤W/2 and every edge has total weight at most W. The formulas give φ(v0)=(0,5] mod 7 = {1,2,3,4,5} and φ(v6)=(18,19] mod 7 = {5}. Since v0 and v6 are adjacent, this is not a proper K-coloring. The induction therefore cannot start. This is not a missing justification; the construction asserted in the paper is wrong.
[Lemma 2.4, induction step] After defining B as the internal vertices of the two ear segments, the proof says: 'By the minimality of F, there is a K-coloring φ of (F^-, w).' This requires F^-=F−B to satisfy all hypotheses of Lemma 2.4, in particular the 'no clique cut' hypothesis. No argument is given that this induced subgraph inherits that property, and it is not automatic: induced subgraphs of graphs without clique cuts can have clique cuts (for example, deleting a vertex from a cycle). If F^- has a clique cutset, the induction hypothesis cannot be applied, and the coloring extension step collapses. This is a second load-bearing gap in the proof of Lemma 2.4.

minor comments (3)

[Near end of Theorem 1.1 proof] The text refers to 'equation (9)', but no display is numbered (9); the intended inequality appears to be the displayed line '2(q−1)(K−W) ≥ w(a)'.
[Lemma 2.5 proof] There is a typographical error in the expression for S: it is written as 'w(v2j +w(v2j+1)' and should be 'w(v2j)+w(v2j+1)'.
[Lemma 2.4, base case] The sentence 'by symmetry, we may assume w(v_{2r}) ≤ W/2' should be justified explicitly: after relabeling the cycle, one can choose a vertex whose weight is at most W/2, but the vertex must also fit the subsequent interval formulas. This is subsumed by the main base-case error, but clarity would help in a revision.

Circularity Check

0 steps flagged

No significant circularity; the proof derives the theorem from external structural lemmas, not from its own conclusion.

full rationale

The paper's argument is a conventional structural derivation: Theorem 1.1 is reduced to Lemma 2.4 via Lemma 2.2 (clique blowup plus universal clique), and Lemma 2.4 is proved by induction using the external decomposition theorem of Conforti et al. [10] and the structural result of Cameron et al. [3]. The target bound is not assumed; the induction is on the skeleton F, and the coloring is constructed from an odd-cycle base case and ear-addition extension. There are no fitted parameters called predictions, no renaming of a known empirical pattern, and no self-citation chain forcing the conclusion. The only prior-work dependencies are external: [10], [3], and the Chen-Xu-Xu result [4] used in Corollary 1.2 for the already-known q=2 case; none is authored by Deng and Zhu, and none assumes the q≥3 theorem. The skeptical reviewer's concerns about the odd-cycle base-case coloring and about F^- inheriting the no-clique-cut property are potential correctness gaps in the proof, but they are not circularity: they do not make the derivation equivalent to its inputs. Therefore the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The proof rests on two substantial cited structure theorems and two unstated assumptions: that (cap, even hole)-free non-perfect graphs contain odd holes rather than odd anti-holes, and that the induced subgraph F⁻ after ear removal inherits the no-clique-cut property needed for the induction. No free parameters or invented entities are introduced.

axioms (5)

standard math Strong Perfect Graph Theorem: every non-perfect graph contains an odd hole or an odd anti-hole.
Used in Section 2 to assert that the minimal counterexample G contains an odd hole, via the statement 'Since G is not perfect and even-hole-free, it contains an odd hole.'
domain assumption Structure of triangle-free odd-signable graphs (Lemma 2.1, Conforti et al. [10]).
Invoked in Section 2 to decompose the skeleton F by good ear additions, which is the core of the inductive proof.
domain assumption Structure of (cap, 4-hole)-free graphs (Lemma 2.2, Cameron et al. [3]).
Invoked in Section 2 to assert that the minimal counterexample G is a clique blow-up of a triangle-free skeleton F.
domain assumption A non-perfect (cap, even hole)-free graph contains an odd hole, not merely an odd anti-hole.
Asserted without proof in Section 2: 'Since G is not perfect and even-hole-free, it contains an odd hole.' This requires more than SPGT, since an odd anti-hole is also possible, and the exclusion of odd anti-holes for this graph class is not shown or cited.
ad hoc to paper The induced subgraph F⁻ = F−B inherits the 'no clique cutset' property from F.
Used in the proof of Lemma 2.4 when the minimality of F is invoked to color F⁻. No justification is given that F⁻ satisfies the no-clique-cut hypothesis of Lemma 2.4.

reviewed 2026-08-01 · how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal binding function for (cap,even hole)-free graphs with no short odd holes." pith.science (2026). https://pith.science/paper/I2M4P6VX

@misc{pith2026260727850,
  author       = {Pith},
  title        = {Pith review of: Optimal binding function for (cap,even hole)-free graphs with no short odd holes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I2M4P6VX}},
  note         = {Machine review of arXiv:2607.27850}
}

Share X Bluesky LinkedIn Reddit HN

abstract

A hole in a graph is an induced cycle of length at least $4$. A cap is a hole together with a vertex adjacent to exactly two consecutive vertices of it. Chen, Xu and Xu conjectured that if $q\ge2$ and $G$ is a $(\mathrm{cap},\mathrm{even\ hole})$-free graph with no odd hole of length at most $2q-1$, then $\chi(G)\le \left\lceil \frac{2q+1}{2q}\omega(G)\right\rceil.$ They confirmed the conjecture for $q \le 3$. In this paper, we prove the conjecture for all $q \ge 3$. As a corollary, we prove that for such a graph $G$, $\chi_f(G)\le \frac{2q+1}{2q}\omega(G).$

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 1 linked inside Pith

[1]

C. Berge. F¨ arbung von graphen, deren s¨ amtliche bzw. deren ungerade kreise starr sind. Wissenschaftliche Zeitschrift der Martin-Luther-Universit¨ at Halle-Wittenberg, Mathematisch- Naturwissenschaftliche Reihe, 10:114–115, 1961

1961
[2]

Bria´ nski, J

M. Bria´ nski, J. Davies, and B. Walczak. Separating polynomial χ-boundedness from χ- boundedness.Combinatorica, 44(1):1–8, 2024

2024
[3]

Cameron, M

K. Cameron, M. V. G. da Silva, S. Huang, and K. Vuˇ skovi´ c. Structure and algorithms for (cap,even hole)-free graphs.Discrete Mathematics, 341(2):463–473, 2018

2018
[4]

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

Pith/arXiv arXiv 2025
[5]

Chudnovsky, N

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

2006
[6]

Chudnovsky, A

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

2017
[7]

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. B, 140:84–97, 2020

2020
[8]

Chudnovsky, A

M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Polynomial bounds for chromatic number VII. Disjoint holes.J. Graph Theory, 104(3):499–515, 2023

2023
[9]

Chudnovsky and P

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

2023
[10]

Triangle-free graphs that are signable without even holes.J

Michele Conforti, G´ erard Cornu´ ejols, Ajai Kapoor, and Kristina Vuˇ skovi´ c. Triangle-free graphs that are signable without even holes.J. Graph Theory, 34(3):204–220, 2000

2000
[11]

P. Erd˝ os. Graph theory and probability.Canadian J. Math., 11:34–38, 1959

1959
[12]

Esperet.Graph colorings, topological coverings and nowhere-zero flows

L. Esperet.Graph colorings, topological coverings and nowhere-zero flows. PhD thesis, Universit´ e Grenoble Alpes, 2017. Habilitation ` a diriger des recherches

2017
[13]

Gy´ arf´ as

A. Gy´ arf´ as. On Ramsey covering-numbers. InInfinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd˝ os on his 60th birthday), Vols. I, II, III, volume Vol. 10 ofColloq. Math. Soc. J´ anos Bolyai, pages 801–816. North-Holland, Amsterdam-London, 1975

1973
[14]

Gy´ arf´ as

A. Gy´ arf´ as. Problems from the world surrounding perfect graphs.Zastos. Mat., 19(3-4):413–441, 1987

1987
[15]

Scott and P

A. Scott and P. Seymour. Induced subgraphs of graphs with large chromatic number. I. Odd holes.J. Combin. Theory Ser. B, 121:68–84, 2016

2016
[16]

A survey of χ-boundedness.J

Alex Scott and Paul Seymour. A survey of χ-boundedness.J. Graph Theory, 95(3):473–504, 2020

2020
[17]

D. P. Sumner. Subtrees of a graph and the chromatic number. InThe theory and applications of graphs (Kalamazoo, Mich., 1980), pages 557–576. Wiley, New York, 1981

1980
[18]

Wu and B

R. Wu and B. Xu. A note on chromatic number of ( cap,even hole )-free graphs.Discrete Mathematics, 342(3):898–903, 2019

2019
[19]

Y. Xu. A better upper bound on the chromatic number of ( cap,even-hole )-free graphs.Discrete Mathematics, 344(11):112581, 2021. 8

2021

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

[1] [1]

C. Berge. F¨ arbung von graphen, deren s¨ amtliche bzw. deren ungerade kreise starr sind. Wissenschaftliche Zeitschrift der Martin-Luther-Universit¨ at Halle-Wittenberg, Mathematisch- Naturwissenschaftliche Reihe, 10:114–115, 1961

1961

[2] [2]

Bria´ nski, J

M. Bria´ nski, J. Davies, and B. Walczak. Separating polynomial χ-boundedness from χ- boundedness.Combinatorica, 44(1):1–8, 2024

2024

[3] [3]

Cameron, M

K. Cameron, M. V. G. da Silva, S. Huang, and K. Vuˇ skovi´ c. Structure and algorithms for (cap,even hole)-free graphs.Discrete Mathematics, 341(2):463–473, 2018

2018

[4] [4]

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

Pith/arXiv arXiv 2025

[5] [5]

Chudnovsky, N

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

2006

[6] [6]

Chudnovsky, A

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

2017

[7] [7]

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. B, 140:84–97, 2020

2020

[8] [8]

Chudnovsky, A

M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Polynomial bounds for chromatic number VII. Disjoint holes.J. Graph Theory, 104(3):499–515, 2023

2023

[9] [9]

Chudnovsky and P

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

2023

[10] [10]

Triangle-free graphs that are signable without even holes.J

Michele Conforti, G´ erard Cornu´ ejols, Ajai Kapoor, and Kristina Vuˇ skovi´ c. Triangle-free graphs that are signable without even holes.J. Graph Theory, 34(3):204–220, 2000

2000

[11] [11]

P. Erd˝ os. Graph theory and probability.Canadian J. Math., 11:34–38, 1959

1959

[12] [12]

Esperet.Graph colorings, topological coverings and nowhere-zero flows

L. Esperet.Graph colorings, topological coverings and nowhere-zero flows. PhD thesis, Universit´ e Grenoble Alpes, 2017. Habilitation ` a diriger des recherches

2017

[13] [13]

Gy´ arf´ as

A. Gy´ arf´ as. On Ramsey covering-numbers. InInfinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd˝ os on his 60th birthday), Vols. I, II, III, volume Vol. 10 ofColloq. Math. Soc. J´ anos Bolyai, pages 801–816. North-Holland, Amsterdam-London, 1975

1973

[14] [14]

Gy´ arf´ as

A. Gy´ arf´ as. Problems from the world surrounding perfect graphs.Zastos. Mat., 19(3-4):413–441, 1987

1987

[15] [15]

Scott and P

A. Scott and P. Seymour. Induced subgraphs of graphs with large chromatic number. I. Odd holes.J. Combin. Theory Ser. B, 121:68–84, 2016

2016

[16] [16]

A survey of χ-boundedness.J

Alex Scott and Paul Seymour. A survey of χ-boundedness.J. Graph Theory, 95(3):473–504, 2020

2020

[17] [17]

D. P. Sumner. Subtrees of a graph and the chromatic number. InThe theory and applications of graphs (Kalamazoo, Mich., 1980), pages 557–576. Wiley, New York, 1981

1980

[18] [18]

Wu and B

R. Wu and B. Xu. A note on chromatic number of ( cap,even hole )-free graphs.Discrete Mathematics, 342(3):898–903, 2019

2019

[19] [19]

Y. Xu. A better upper bound on the chromatic number of ( cap,even-hole )-free graphs.Discrete Mathematics, 344(11):112581, 2021. 8

2021

Optimal binding function for (cap,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