Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

The optimal binding function for (cap, even hole)-free graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Every (cap, even hole)-free graph can be colored with at most 5/4 times its clique number; forbidding 5-holes lowers the multiplier to 7/6.

desk verdict Solves a 2018 open problem with a reusable reduction theorem, but Section 4.1 has an unproved existence claim for F that needs a fix. read the letter →

arxiv 2506.19580 v1 pith:AN2WD5E4 submitted 2025-06-24 math.CO

Ran Chen , Baogang Xu , Yian Xu This is my paper · ORCID
classification math.CO MSC 05C1505C75
keywords capevenholechromaticnumbercliquebindingfunctionblowupodd-signablegraphspathextension
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 a best-possible coloring bound for graphs containing neither a cap nor an even hole. A cap is a hole with one extra vertex adjacent to exactly two consecutive vertices of the hole; an even hole is an induced cycle of even length at least four. The main theorem states that every such graph $G$ satisfies $\chi(G)\le \lceil\frac{5}{4}\omega(G)\rceil$, and if $G$ also has no hole of length five, then $\chi(G)\le \lceil\frac{7}{6}\omega(G)\rceil$; both bounds are attained by specific clique blowups of a 5-hole and a 7-hole. These results settle a question posed in 2018 about the exact linear binding function for this hereditary class. The proof works through a general reduction, Theorem 1.1, which reduces checking a $p/(2q)$ chromatic bound for all clique blowups of a triangle-free graph to checking only blowups with bounded clique number.

What carries the argument

The engine of the proof is Theorem 1.1, a reduction principle for clique blowups. It says that to prove a bound of the form $\chi(G)\le \lceil\frac{p}{2q}\omega(G)\rceil$ for all clique blowups of a triangle-free graph $F$, it is enough to check the bound only on those blowups whose clique number is at most $\max\{\frac{2q(p-q-2)}{p-2q},2q\}$. The proof carves a small set $T$ of vertices out of each bag, splits the remainder into two parts $V_1$ and $V_2$ with controlled clique numbers, colors each part by induction, and recombines the colorings. To connect this to the target class, the paper uses two structural theorems as black boxes: Lemma 2.2, which expresses a (cap, 4-hole)-free graph with a hole and no clique cutset (a clique whose removal disconnects the graph) as a clique blowup of a maximal triangle-free induced subgraph together with a universal clique (a clique complete to the rest of the graph), and Lemma 2.1, which builds triangle-free odd-signable graphs from a hole by controlled ear additions called good ear additions. The base cases of small clique number are handled by a path-extension coloring technique, which greedily extends a partial coloring along blown-up paths.

What would settle it

Run an exact search over all (cap, even hole)-free graphs on up to fourteen vertices, computing $\chi(G)$ and $\omega(G)$; any output with $\chi(G)>\lceil\frac{5}{4}\omega(G)\rceil$ would refute the main theorem. The known equality cases—uniformly blown-up 5-holes and 7-holes—should appear with equality, and a violation of the analogous small-clique condition in Theorem 1.1 could be checked directly by constructing a triangle-free $F$ and choosing bag sizes just above the stated threshold.

Watch

Extended reading notes

Core claim

At the level of the paper's own claims, the central discovery is a reduction and two sharp bounds. Theorem 1.1 says that for positive integers $p>2q$ and any triangle-free graph $F$, the inequality $\chi(G)\le \lceil\frac{p}{2q}\omega(G)\rceil$ holds for every clique blowup $G$ of $F$ as soon as it holds for those blowups with clique number at most $\max\{\frac{2q(p-q-2)}{p-2q},2q\}$. The paper then proves, by induction and structural decomposition, that every (cap, even hole)-free graph satisfies $\chi(G)\le \lceil\frac{5}{4}\omega(G)\rceil$, answering a 2018 question in the affirmative, and that every such graph with no 5-hole satisfies $\chi(G)\le \lceil\frac{7}{6}\omega(G)\rceil$. Uniform clique blowups of a 5-hole and of a 7-hole show the constants cannot be lowered, so the binding functions are optimal.

Load-bearing premise

The load-bearing premise is that the two structural classifications imported from earlier work—one describing triangle-free odd-signable graphs as built from a hole by controlled ear additions, the other describing (cap, even hole)-free graphs as clique blowups of such a triangle-free graph plus a universal clique—hold for every graph in the class; if either fails, the coloring bound is not established.

Editorial extensions

If this is right

  • Every (cap, even hole)-free graph can be colored with at most $\frac{5}{4}$ of its clique number; this is the exact linear binding function for the class.
  • Adding the absence of 5-holes improves the guarantee to $\frac{7}{6}$ of the clique number, also tight.
  • Theorem 1.1 reduces any $p/(2q)$ coloring bound for clique blowups of a triangle-free graph to the case of bounded clique number, which can make such bounds easier to verify.
  • The reachability examples mean no smaller multiplier of $\omega$ can serve as a universal bound for either class.

Reading between the lines

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

  • The closing remark suggests the pattern continues: for graphs whose shortest odd hole has length at least $2q+1$, the conjectured bound is $\chi\le \lceil\frac{2q+1}{2q}\omega\rceil$; this paper settles the cases $q=2$ and $q=3$, so $q=4$ is the immediate next test.
  • Because Theorem 1.1 is stated for arbitrary triangle-free $F$, the same reduction could transfer coloring bounds between very different hereditary classes once a structural decomposition into clique blowups is known.
  • The path-extension coloring argument is constructive, so the proof likely gives an efficient coloring algorithm when the clique number is bounded, though the paper does not claim this.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies χ-binding functions for (cap, even hole)-free graphs. It first proves a reduction theorem (Theorem 1.1) for clique blowups of a triangle-free graph F: with p>2q, proving χ(G)≤⌈p/(2q)ω(G)⌉ for all clique blowups of F is reduced to proving it only for blowups with clique number at most max{2q(p−q−2)/(p−2q), 2q}. The proof is by induction and removes a set T of size q from each bag, decomposing the remainder into two anticomplete parts. The paper then invokes structural characterizations of (cap, even hole)-free graphs without clique cutsets as clique blowups of triangle-free graphs obtainable by good ear additions, and proves by a lengthy case analysis (Lemma 4.1) the required bound for small clique number: χ≤⌈5/4ω⌉ for K5-free graphs and χ≤⌈7/6ω⌉ for (5-hole,K13)-free graphs. Theorem 1.2 follows by combining these pieces, and both bounds are shown tight by clique blowups of 5- and 7-holes, answering a question of Cameron et al.

Significance. If correct, this settles an open problem and improves the previous best bound for (cap, even hole)-free graphs. The reduction Theorem 1.1 is a clean and potentially reusable tool; the numerical inequalities in its proof are sound, and the ceiling slack is used correctly. The examples attaining the bounds are simple and convincing. The main caveats are two load-bearing presentation and support issues: the statement of Theorem 1.1 is misquantified, and the existence of a maximal triangle-free induced subgraph without a clique cutset is asserted rather than proved or cited. Both are fixable without changing the main idea.

major comments (2)
  1. [Theorem 1.1 and Abstract] The quantification of G′ is not the one used in the proof. As written, the theorem fixes one G′ with ω(G′)≤max{2q(p−q−2)/(p−2q), 2q} and asserts an equivalence between 'for every clique blowup G' and 'χ(G′)≤⌈p/(2q)ω(G′)⌉'. For a single fixed G′, the right-hand side cannot control all unbounded blowups. The proof and the applications in Section 4 require the hypothesis that every clique blowup G′ with ω(G′)≤M satisfies the inequality. Please restate Theorem 1.1 as a reduction: if every bounded-clique-number blowup of F satisfies the bound, then every clique blowup of F satisfies the bound, with the converse being immediate.
  2. [Section 4 and Section 4.1] The proof asserts, without proof or citation, that one may choose a maximal triangle-free induced subgraph F of G with no clique cutset. This appears in the proof of Theorem 1.2 ('we may choose a maximal triangle-free induced subgraph F of G which has no clique cutset') and again in both halves of Lemma 4.1. Lemmas 2.1 and 2.2 apply only to an F that already has no clique cutset; minimality of G and the absence of clique cutsets in G do not by themselves imply such an F exists. This assertion is the entry point for both the blowup structure and the good-ear decomposition, and hence for the entire case analysis. Please either prove this assertion or cite the precise theorem in [2] or [10] that guarantees it. If it is a known result, it should be stated in Section 2.
minor comments (4)
  1. [Lemma 4.2 and References] Lemma 4.2 is quoted from the authors' own arXiv preprint [4]. Since it is used both in the base case of Lemma 4.1 and in establishing reachability of the bounds, please include a short proof in the paper or cite a published source.
  2. [Claim 4.5] In the displayed formula before coloring X_{2m2−2}, the indices X_{2m1−1} and X_{2m1−3} appear where X_{2m2−1} and X_{2m2−3} are clearly intended; this makes the estimate hard to follow.
  3. [Section 3 and Section 4.1] The claim that V1\T is a union of pairwise anticomplete cliques is compressed; spelling out why a vertex of F cannot be incident with two V1-edges using ω(G)≥2q+1 would improve readability.
  4. [Throughout] There are several typos, including 'maximal triangle-free induced subgraph graph' in Section 4.1 and 'for for each odd integer' in Claim 4.3. Proofreading is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the bounds follow from an independently proved reduction theorem plus external structural lemmas; the only self-citation is an auxiliary odd-hole blowup coloring result.

full rationale

The derivation chain is not circular. Theorem 1.1 is a self-contained reduction proved by induction on |V(G)|, showing that the bound for all clique blowups follows from the bound for clique blowups with bounded clique number. Theorem 1.2 then applies this reduction to a maximal triangle-free induced subgraph, using Lemma 4.1, which is proved separately by structural decomposition and greedy path-extension arguments. Lemma 4.1 itself invokes Lemmas 2.1 and 2.2, external structural results from Conforti et al. and Cameron et al., and does not assume the target inequality. The cited Lemma 4.2 from Chen and Xu is a self-citation, but it is a distinct specialized result about clique blowups of odd holes, not an encoding of the main theorem, so it does not make the argument circular. One genuine gap, flagged for correctness rather than circularity, is the unproved assertion in Section 4 that a maximal triangle-free induced subgraph F with no clique cutset exists; this is a missing justification but not a reduction of the conclusion to its own input. No equation in the paper identifies the target bound with an input assumption, and no fitted parameter is renamed as a prediction.

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

The central claim rests on structural decomposition theorems from prior work (Lemmas 2.1 and 2.2) and on the self-cited Lemma 4.2 about odd cycle blowups. No parameters are fitted to data; p and q are variables in the theorem statement. No new entities are posited.

assumptions (3)
  • domain assumption Lemma 2.2 (Cameron et al.): every (cap, 4-hole)-free graph with a hole and no clique cutset is a clique blowup of a maximal triangle-free subgraph plus a universal clique.
    Used in Section 4 to reduce (cap, even hole)-free graphs to clique blowups of triangle-free graphs.
  • domain assumption Lemma 2.1 (Conforti et al.): triangle-free odd-signable graphs without clique cutsets, except the cube, are obtained from a hole by good ear additions.
    Used in Lemma 4.1 to restrict the structure of the triangle-free base graph F.
  • domain assumption Lemma 4.2 (Chen and Xu, self-cited): clique blowups of odd holes satisfy χ(G) ≤ ⌈(2q+1)/(2q)ω(G)⌉ and the t-clique blowup attains equality.
    Used to rule out F being an odd hole and to show the bounds are reachable. This is self-cited but is an independent, easily provable statement.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The optimal binding function for (cap, even hole)-free graphs." pith.science (2026). https://pith.science/paper/AN2WD5E4

@misc{pith2026250619580,
  author       = {Pith},
  title        = {Pith review of: The optimal binding function for (cap, even hole)-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AN2WD5E4}},
  note         = {Machine review of arXiv:2506.19580}
}
abstract

A {\em hole} is an induced cycle of length at least 4, an {\em even hole} is a hole of even length, and a {\em cap} is a graph obtained from a hole by adding an additional vertex which is adjacent exactly to two adjacent vertices of the hole. A graph $G$ obtained from a graph $H$ by blowing up all the vertices into cliques is said to be a clique blowup of $H$. Let $p, q$ be two positive integers with $p>2q$, let $F$ be a triangle-free graph, and let $G'$ be a clique blowup of $F$ with $\omega(G')\leq\max\{\frac{2q(p-q-2)}{p-2q}, 2q\}$. In this paper, we prove that for any clique blowup $G$ of $F$, $\chi(G)\leq\lceil\frac{p}{2q}\omega(G)\rceil$ if and only if $\chi(G')\leq\lceil\frac{p}{2q}\omega(G')\rceil$. As its consequences, we show that every (cap, even hole)-free graph $G$ satisfies $\chi(G)\leq\lceil\frac{5}{4}\omega(G)\rceil$, which affirmatively answers a question of Cameron {\em et al.} \cite{CdHV2018}, we also show that every (cap, even hole, 5-hole)-free graph $G$ satisfies $\chi(G)\leq\lceil\frac{7}{6}\omega(G)\rceil$, and the bound is reachable.

Figures

Figures reproduced from arXiv: 2506.19580 by the authors.

Figure 1
Figure 1. Illustration of some forbidden graphs. A cap is a graph consisting of a hole and an additional vertex which has exactly two adjacent neighbors in the hole. The class of (cap, odd hole)-free graphs has been studied extensively (see [9]). Since the complement of an odd hole of length at least 7 contains a cap of order 5, it is easy to see, from the Strong Perfect Graph Theorem, that (cap, odd hole)-free graphs are per… view at source ↗
Figure 2
Figure 2. Illustration of G, P1 and P2. We can easily deduce that ⌈ ω(G) 4 ⌉ < |Xi | < ⌊ 3ω(G) 4 ⌋ for 0 ≤ i ≤ 2m2, and |Y | < ⌊ 3ω(G) 4 ⌋. Since 2 ≤ ω(G) ≤ 4, we have that |Xi | = 2 for 0 ≤ i ≤ 2m2, and 1 ≤ |Y | ≤ 2. Therefore, ω(G) = 4, and χ(G) > 5. Since G is a minimum counterexample, there exists a 5-coloring ϕ: V (G − S2m2−1 i=1 Xi) → [5], where [5] = {1, · · · , 5}. Now we deduce a contradiction by using two steps of p… view at source ↗
Figure 3
Figure 3. Illustration of G and P1. We first color |S| vertices of Xj with the colors in S when j is even in {2, 4, . . . , 2m1−4}, and greedily color all vertices of X2m1−2 using as many colors in S as possible. Denote the resulted partial extension of ϕ as ϕ1. Then, we start from X2m1−4, and extend ϕ1 to ϕ2 that colors sequentially all uncolored vertices of Xj for even j in {2m1 − 4, . . . , 2}, such that |ϕ2(Xj+2) ∩ ϕ2(Xj … view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

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

    math.CO 2026-07 reject novelty 6.0 of 10

    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...

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

    math.CO 2026-07 conditional novelty 6.0 of 10

    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.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages · cited by 2 Pith papers

  1. [2]

    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, Disc. Math. 341 (2018) 463-473

    work page 2018

  2. [3]

    Cameron, S

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

    work page 2018

  3. [10]

    Conforti, G

    M. Conforti, G. Cornu´ ejols, A. Kapoor and K. Vuˇ skovi´ c, Triangle-free graphs that are signable without even holes, J. Graph Theory 34 (2000) 204-220

    work page 2000

  4. [1]

    J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, New York, 2008

    2008

  5. [4]

    Nearly optimal coloring of some C4-free graphs

    R. Chen and B. Xu, Nearly optimal coloring of some C4-free graphs, arXiv:2409.06944, 2024

    work page Pith review arXiv 2024

  6. [5]

    Chudnovsky, N

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

    work page 2006

  7. [6]

    Chudnovsky, A

    M. Chudnovsky, A. Scott and P. Seymour, Induced subgraphs of graphs with large chro- matic number. III Long holes, Combinatorica 37 (6) (2017) 1057-1072

    work page 2017

  8. [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. Comb. Theory B 140 (2020) 84-97

    work page 2020

Show all 23 references
  1. [8]

    Chudnovsky and P

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

    2023

  2. [9]

    Conforti, G

    M. Conforti, G. Cornu´ ejols, A. Kapoor and K. Vuˇ skovi´ c, Even and odd holes in cap-free graphs, J. Graph Theory 30 (1999) 289 ¨C308

    1999

  3. [11]

    G. A. Dirac, On rigid circuit graphs, Abh. Math. Semin. Univ. Hambg. (1961) 71-76

    1961

  4. [12]

    Erd˝ os, Graph theory and probability, Canad

    P. Erd˝ os, Graph theory and probability, Canad. J. Math. 11 (1959) 34-38

    1959

  5. [13]

    D. J. Fraser, A. M. Hamel and C. T. Hoang, On the structure of (even-hole, kite)-free graphs, Graphs and Combinatorics, 34 (2018) 989-999

    2018

  6. [14]

    Gy´ arf´ as, On Ramsey covering-numbers, Infinite and Finite Sets 2 (1975) 801-816

    A. Gy´ arf´ as, On Ramsey covering-numbers, Infinite and Finite Sets 2 (1975) 801-816

    1975

  7. [15]

    Gy´ arf´ as, Problems from the world surrounding perfect graphs, Zastosow

    A. Gy´ arf´ as, Problems from the world surrounding perfect graphs, Zastosow. Mat. 19 (1987) 413-441

    1987

  8. [16]

    Kloks, H

    T. Kloks, H. M¨ uller and K. Vuˇ skovi´ c, Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences, J. Combin. Theory Ser. B 99 (2009) 733-800. 14

    2009

  9. [17]

    Ramirez-Alfonsin and B

    J. Ramirez-Alfonsin and B. Reed (Eds.), Perfect Graphs, Wiley, Chichester, 2001, pp 130

    2001

  10. [18]

    Schiermeyer and B

    I. Schiermeyer and B. Randerath, Polynomial ¦ ¨O-binding functions and forbidden induced subgraphs: a survey, Graphs Comb. 35 (1) (2019) 1-31

    2019

  11. [19]

    Scott and P

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

    2016

  12. [20]

    V. G. Vizing, The chromatic class of a multigraph, Kibernetika(kiev) 3 (1965) 29-39

    1965

  13. [21]

    Vuˇ skovi´ c, Even-hole-free graphs: a survey, Appl

    K. Vuˇ skovi´ c, Even-hole-free graphs: a survey, Appl. Anal. Discrete Math. 4 2 (2010) 219-240

    2010

  14. [22]

    Wu and B

    R. Wu and B. Xu, A note on chromatic number of (cap, even hole)-free graphs, Disc. Math. 342 (2019) 898-903

    2019

  15. [23]

    Xu, A better upper bound on the chromatic number of (cap, even hole)-free graphs, Disc

    Y. Xu, A better upper bound on the chromatic number of (cap, even hole)-free graphs, Disc. Math. 344 (2021) 112581. 15

    2021

Pith tools

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