On $k$-colorability of $(bull, H)$-free graphs

Ingo Schiermeyer; Magdalena Prorok; Monika Pil\'sniak; Nadzieja Hodur

REVIEW 4 major objections 5 minor 1 cited by

On $k$-colorability of $(bull, H)$-free graphs

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

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

Pith's one-line read Odd-cycle clique expansions are k-colorable exactly when two simple size inequalities hold, and this yields complete classifications of all non-4- and non-5-colorable graphs in several bull-free families.

desk verdict Real new results, but the main theorems are false as written because C_p⊕K_j silently means the join of an odd antihole, not a cycle. read the letter →

arxiv 2509.01698 v1 pith:LH5OGA24 submitted 2025-09-01 math.CO

Nadzieja Hodur , Monika Pilśniak , Magdalena Prorok , Ingo Schiermeyer This is my paper · ORCID

classification math.CO MSC 05C1505C1768Q2568W40

keywords 4-colorability5-colorabilitybull-freegraphsclaw-freecliqueexpansionofoddcyclesforbiddeninducedsubgraphsperfectchromaticnumber

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 gives a complete arithmetic test for coloring "clique expansions" of odd cycles: replace each vertex of an odd cycle by a clique, joining consecutive cliques completely. For such a graph, k-colorability holds exactly when every pair of neighboring cliques has at most k vertices total and the whole graph has at most nk vertices, where the cycle has 2n+1 positions. Using that test, the authors classify every connected graph that contains no bull (a triangle with two pendant edges) and no claw (three leaves joined to one center) and is not 4-colorable: it must contain one of a short list of explicit induced subgraphs. Analogous complete dichotomies are proved for non-4-colorable (bull, chair, C5)-free graphs and for non-5-colorable (bull, claw, C5)-free graphs, where the chair is a claw with one leg subdivided. The upshot is that in these families, deciding k-colorability reduces to checking a finite list of named obstructions.

What carries the argument

The central object is the clique expansion C_p[k_1,...,k_p]—a cycle whose vertices are replaced by cliques of specified sizes, with all edges between consecutive cliques. The load-bearing identity is the pair of inequalities in Theorem 4, which turn k-colorability into arithmetic. Around it, the proofs rely on the Strong Perfect Graph Theorem to split non-perfect graphs into odd-hole and odd-antihole cases; on structural facts (Lemma 14, Lemma 15, Fact 19) describing how a vertex outside an odd antihole or odd cycle can attach to it without creating a bull, claw, or chair; and on the identity χ(G)=n−β0(G) for graphs with independence number 2, which controls the 5-colorability cases.

What would settle it

Decide the convention for C7 in the exception list of Theorem 6. If C7 means the ordinary 7-cycle, then the graph made by joining a single new vertex to every vertex of the complement of a 7-cycle is a 5-chromatic (bull,claw)-free graph not on the list, so the exception list would be incomplete; if C7 means the complement of the 7-cycle, the listed graph is exactly that obstruction. Checking which graph a 4-colorability solver computes as 5-chromatic settles which reading the theorem requires.

Watch

Extended reading notes

Core claim

At the core is Theorem 4: a clique expansion C_{2n+1}[k_1,...,k_{2n+1}] is k-colorable exactly when k_i+k_{i+1}≤k for every i and the sum of the k_i is at most nk. The two inequalities are necessary by a color-repetition count around the cycle and sufficient by the circular k-coloring algorithm. The dichotomy theorems (Theorems 6–8) then use the Strong Perfect Graph Theorem and structural lemmas to reduce any non-perfect (bull,claw)-free graph either to such a clique expansion or to an odd antihole with tightly constrained outside attachment; each case leads to one of the listed exceptional subgraphs.

Load-bearing premise

The exception lists in Theorems 6–8 use C7 to mean the complement of a 7-cycle (a graph whose non-edges form a 7-cycle), not the ordinary cycle itself; all the classification proofs rely on that convention.

Editorial extensions

If this is right

For any clique expansion of an odd cycle, checking k-colorability requires no search: just verify the two inequalities.
Every connected (bull,claw)-free graph that is not 4-colorable contains one of the listed induced subgraphs, so the obstructions give a finite certificate for non-4-colorability in this class.
Every connected (bull,claw,C5)-free graph that is not 5-colorable is either large with independence number 2, has a vertex of degree at least 9, or contains one of the listed clique/cycle obstructions; otherwise it is 5-colorable.
Corollary 5 extends the 3-colorability dichotomies from earlier work to arbitrary k for (bull,claw)-free graphs with an induced cycle of length at least 7 and independence number at least 3.

Reading between the lines

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

The paper leaves implicit that Theorem 4 gives a polynomial-time decision procedure for k-colorability of odd-cycle clique expansions, since the two inequalities can be checked in time linear in the number of cliques.
The same total-vertex-count condition looks like a prototype for k-colorability of clique expansions of other base graphs: the local condition controls adjacent cliques, and the global condition controls how colors wrap around a cycle.
Because the exception lists in Theorems 6 and 8 are all small gadgets joined to a large clique or cycle, an algorithmic recognizer for these classes could test non-colorability by checking induced subgraphs up to a fixed size rather than solving a general coloring instance.

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.

Desk Editor's Note

read the letter

The thing to know about this paper is that it has a genuinely useful new result and a load-bearing notation bug. Theorem 4, the criterion for k-colorability of clique expansions of odd cycles, looks new and is the cleanest part. The 4- and 5-colorability dichotomies for (bull,claw)-free and related classes are also new extensions beyond the earlier 3-color results, and the overall strategy — use the Strong Perfect Graph Theorem, then split into odd-hole/odd-antihole cases — is sound.

But the theorems as stated are false. The paper defines C_p as an induced cycle, yet uses C7⊕K1 and C9⊕K1 in the exception lists to name what are actually joins of odd antiholes with K_j. Under the literal definition, C7⊕K1 is the wheel W7, which is 4-colorable and contains a claw, so it cannot be the non-4-colorable (bull,claw)-free exception in Theorem 6. The same problem hits Theorem 8(iii). The stress-test's example is exact: the intended graph \overline{C7}⊕K1 has chromatic number 5 and is (bull,claw)-free, and it isn't covered by any other item of Theorem 6. So the main dichotomy theorems are not merely imprecisely written; they are wrong as printed.

There are also smaller issues. Fact 18 and Fact 23 are given with only a one-line justification, and the sufficiency direction of Theorem 4 is argued in a paragraph and a half — all three need real proofs for a referee to check. The paper leans heavily on unpublished self-cited manuscripts [5], [11], [12], which is a burden, though not disqualifying if those manuscripts are made available.

What's good: the ideas are right. The structural lemmas (Fact 19–21 in the (bull,chair)-free case, the clique-expansion reduction) point to a correct proof once the notation is fixed. I suspect the paper is salvageable with a careful revision: change C_p to \overline{C_p} in the exception names, add the missing proof details, and make the dependence on the unpublished papers explicit.

For a referee: yes, this deserves serious refereeing, but not acceptance in its current form. I'd ask for major revision. It's the kind of paper I'd bring up in reading group to talk about how notation can silently invert a theorem.

Referee Report

4 major / 5 minor

Summary. The paper studies k-colorability of graphs that are bull-free and additionally claw-free or chair-free. Its main results are: Theorem 4, a necessary and sufficient criterion for k-colorability of a clique expansion of an odd cycle (consecutive clique sizes sum at most k and total size at most nk); Theorems 6 and 7, structural dichotomies for non-4-colorable connected (bull,claw)-free and (bull,chair,C5)-free graphs; and Theorem 8, a dichotomy for non-5-colorable connected (bull,claw,C5)-free graphs. The proofs use the Strong Perfect Graph Theorem, structure theorems for (bull,claw)-free graphs from [4], and local arguments about neighborhoods of an odd hole or antihole, with some reliance on unpublished manuscripts [5], [11], [12].

Significance. If established, these results are substantial: Theorem 4 provides a clean, falsifiable criterion for all clique expansions of odd cycles, and Theorems 6 and 8 would give complete obstruction lists for 4- and 5-colorability in structured hereditary classes, with potential consequences for coloring algorithms. The paper is well organized and the overall strategy is plausible. However, as written, the statements are not reliable because of a load-bearing notational inconsistency, and several proof steps are only sketched. The results do not yet meet the standard of a fully verified characterization.

major comments (4)

[Section 1 and Sections 5.2, 6.1, 7.2] The definition of C_p as an induced cycle is inconsistent with its use in the main theorems. In §5.2, Q is an odd antihole; when a vertex dominates Q, the paper says the exceptional graph is C7⊕K1. Literally, C7⊕K1 is the wheel W7, which contains a claw and is 4-colorable, so it cannot be the non-4-colorable (bull,claw)-free obstruction. The intended graph is \overline{C7}⊕K1. The same issue affects Theorem 8(iii) (C9⊕K1) and Theorem 7(i). In contrast, Theorem 7(ii) is generated from an actual induced cycle in §6.2, so a global redefinition of C_p as antihole would also be wrong. Thus the three main dichotomy theorems, as stated, have no consistent reading under which they are true. This is load-bearing and must be fixed by introducing \overline{C_p} (or equivalent notation) and re-verifying each occurrence.
[Section 5.2, Fact 18] Fact 18 is stated without proof: it asserts that if w,w' are adjacent to an odd antihole Q and N(w)∪N(w')≠Q, then ww' is an edge. This fact is used in the p=7 case to force K5 or the clique expansion C[1,3,1,3,1], and again in the p=5 case. Since this inference is load-bearing for Theorem 6, a proof or citation must be supplied.
[Section 4, proof of Theorem 4] The sufficiency direction of Theorem 4 is not actually proved. The text says 'It is easy to show' and describes a coloring after finding an index l, but the existence of l is asserted without a rigorous argument, and the coloring of the intervening cliques is not fully specified. Condition (i) is not visibly used in the sufficiency argument. Since Theorem 4 is used to derive Corollary 5 and Theorem 8(vi), a complete proof is needed.
[Section 7.2, Fact 23] Fact 23 (H is complete) is only a short sketch. The steps 'Then w3∈C' and 'Since Δ(G)≤8, we may assume w1w3∉E(G)' are not justified. This fact is used to reduce the 10-vertex case in Theorem 8, so these gaps need to be filled.

minor comments (5)

[Theorem 4 and Corollary 5] The phrase 'all indices are taken modulo k' should refer to the cycle length (2n+1 or p), not the number of colors k.
[Introduction and Section 4] Typos: 'without loosing generality' should be 'without losing generality'; also 'F act' appears in Section 5.2.
[Lemma 16] The sentence 'Suppose that Q ̸= C5 = C5' is nonsensical; it should be something like 'Suppose Q is not isomorphic to C5'.
[Fact 19 proof] In the proof of Fact 19, the case ℓ=2 says the set {v_{k-1}, v_k, w, v_{k+1}, v_{k+2}} induces a bull. The notation and the argument for why this is a bull should be made explicit, especially since the figure reference is not fully self-contained.
[Section 7.2] After fixing the C_p notation, the isomorphisms 'G ∼= C9⊕K1' and 'G ∼= C7⊕K2' in the proof of Theorem 8 need to be updated consistently (e.g., to \overline{C9}⊕K1 and \overline{C7}⊕K2).

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction in the core derivation chain; Theorem 4 is self-contained and Theorems 6–8 are built on external structure theorems. The paper has minor self-citation dependencies and a load-bearing notation error in the exception names, but these are not circularity.

full rationale

The central result, Theorem 4, is proven directly: the necessity of ki+ki+1 <= k and sum ki <= nk is obtained from a coloring/counting argument on clique expansions, and sufficiency is shown by explicitly constructing the k-CC coloring. No condition of Theorem 4 is assumed from the conclusions it is used to prove. Theorems 6–8 are derived by combining the Strong Perfect Graph Theorem, published results of Brause et al. [4], Ben Rebea’s lemma [1], and Theorem 4; there is no fitted parameter, no quantity is renamed and then predicted, and the characterizations are not restatements of their inputs. The proof of Theorem 7 does invoke an unpublished self-cited manuscript: “By Theorem 3 we know that G \ D is 3-colorable if and only if it does not contain an odd wheel or a spindle graph M3i+1” ([12]). This is a load-bearing dependency, but it is a theorem about 3-colorability of (bull,chair)-free graphs, not about 4-colorability of (bull,chair,C5)-free graphs; it is therefore not equivalent to the paper’s new conclusion. A separate correctness hazard is the notation for exceptional graphs: Section 1 defines C_p as an induced cycle, while Sections 5.2 and 7.2 use “C7 ⊕ K1” and “C9 ⊕ K1” to name the join of an odd antihole Q with K1. As literally written, those exceptions would be wheels, which are not (bull,claw)-free obstructions with the stated chromatic behavior; the intended graphs are antihole joins. This is a load-bearing notational inconsistency, not a circular derivation. Overall, the claimed results are not obtained by assuming the conclusions, and the circularity score is therefore low.

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

The central results rest on external structural theorems, mostly from published [4] and the Strong Perfect Graph Theorem. The paper adds a new clique-expansion criterion and new dichotomies, but the proof of Theorem 7 depends on an unpublished self-cited theorem, and the notation for exceptional graphs introduces an implicit redefinition of C_p.

assumptions (5)

standard math Strong Perfect Graph Theorem (Theorem 9)
Used to restrict non-perfect graphs to odd holes or odd antiholes in the proofs of Theorems 6, 7, and 8.
domain assumption Theorem 10 from [4]: connected (bull,claw)-free graphs with alpha(G) >= 3 are perfect or clique expansions of odd cycles of length at least 7
Cornerstone of Section 5.1 and Theorem 8; taken from a published paper by Brause et al.
domain assumption Theorem 11 from [4]: structural properties of (bull,claw)-free graphs
Used to derive Corollary 13 and to justify that long induced cycles force clique expansions.
domain assumption Lemma 12 from [1]: claw-free graphs with alpha >= 3 containing an odd antihole contain an induced C5
Used in Corollary 13 to conclude that odd antiholes in (bull,claw)-free graphs force alpha = 2.
domain assumption Theorem 3 from [12]: 3-colorability dichotomy for (bull,chair)-free graphs
Used in the proof of Theorem 7 to conclude that G minus D is 3-colorable if it lacks odd wheels and spindles; [12] is an unpublished self-cited manuscript.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On $k$-colorability of $(bull, H)$-free graphs." pith.science (2026). https://pith.science/paper/LH5OGA24

@misc{pith2026250901698,
  author       = {Pith},
  title        = {Pith review of: On $k$-colorability of $(bull, H)$-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LH5OGA24}},
  note         = {Machine review of arXiv:2509.01698}
}

abstract

The $3$-colorability problem is a well-known NP-complete problem and it remains NP-complete for $bull$-free graphs, where a $bull$ is the graph consisting of a $K_3$ with two pendant edges attached to two of its vertices. In this paper, for $k\geq3$, we characterize all $k$-colorable $(bull,claw)$-free graphs containing an induced cycle of length at least $6$. Moreover, we present the full characterization of all non $4$-colorable connected $(bull,claw)$-free graphs and $(bull,chair, C_5)$-free graphs, and all non $5$-colorable connected $(bull, claw, C_5)$-free graphs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Perfect divisibility and perfect-Pollyanna in bull-free graphs
math.CO 2026-03 accept novelty 6.5 of 10

Bull-free graphs satisfy the five perfect-divisibility conjectures (P5-, odd/even-hole-, 4K1-, fork-free); (bull,H)-free classes for H in {house,hammer,diamond} are perfect-Pollyanna.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages · cited by 1 Pith paper

[5]

Brause, P

C. Brause, P. Holub, I. Schiermeyer: On 3-colourability, 4-criticality and induced prisms in claw-free graphs, manuscript 2025. 1, 1, 2

work page 2025
[11]

Hodur, M

N. Hodur, M. Pilśniak, M. Prorok, P. Rzążewski, Finding large k-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs, manuscript arXiv:2504.04984, 2025. 6.2

arXiv 2025
[12]

On the distinguishing chromatic number in hereditary graph classes

N. Hodur, M. Pilśniak, M. Prorok, I. Schiermeyer, On 3-colorability of(bull, H)-free graphs, manuscript arXiv:2505.17193, 2025. 1, 3

work page Pith review arXiv 2025
[4]

Brause, P

C. Brause, P. Holub, A. Kabela, Z. Ryjáček, I. Schiermeyer, P. Vrána: On forbidden induced subgraphs for claw-free perfect graphs, Discrete Math. 342 (2019), 1602–

work page 2019
[1]

Ben Rebea: Étude des stables dans les graphes quasi-adjoints (Thèse) Université de Grenoble, France (1981)

A. Ben Rebea: Étude des stables dans les graphes quasi-adjoints (Thèse) Université de Grenoble, France (1981). 12

work page 1981
[2]

J. A. Bondy, U.S.R. Murty: Graph Theory. Springer, 2008. 1

work page 2008
[3]

Brause, T

C. Brause, T. Doan, P. Holub, A. Kabela, Z. Ryjáček, I. Schiermeyer, P. Vrána: Forbidden induced subgraphs and perfectness forK1,3-free perfect graphs of inde- pendence number at least 4, Discrete Math. 345/6, (2022), 112837. 1

work page 2022
[6]

Bruce, C.T

D. Bruce, C.T. Hoàng, J. Sawada: A Certifying Algorithm for3-Colorability of P5- free Graphs, Algorithms and Computation. ISAAC2009. Lecture Notes in Computer Science, 5878 (2009) 594-604

work page 2009

Show all 18 references

[7]

M.Chudnovsky, J.Goedgebeur, O.Schaudt, M.Zhong: Obstructions for three- coloring graphs without induced paths on six vertices. J. Combin. Theory Ser. B 140 (2020), 45–83

2020
[8]

M.Chudnovsky, A.Scott, P.Seymour, S.Spirkl: Detecting an Odd Hole. J. of the ACM 67/1 (2020), A5

2020
[9]

Chudnovsky, N

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

2006
[10]

P. A. Golovach, M. Johnson, D. Paulusma, J. Song: A survey on the computational complexity of coloring graphs with forbidden subgraphs, J. Graph Theory 84 (2017), 331–363. 1, 1

2017
[13]

Randerath, The Vizing bound for the chromatic number based on forbidden pairs, Aachen, Techn

B. Randerath, The Vizing bound for the chromatic number based on forbidden pairs, Aachen, Techn. Hochsch., PhD Thesis, 1998. 1

1998
[14]

Randerath, I

B. Randerath, I. Schiermeyer: Vertex coloring and forbidden subgraphs - a survey, Graphs Combin. 20 (2004), 1–40. 1

2004
[15]

Randerath, I

B. Randerath, I. Schiermeyer: 3-Colorability∈ Pfor P6-free Graphs, Discrete Appl. Math. 136 (2004), 299–313. 1

2004
[16]

Randerath, I

B. Randerath, I. Schiermeyer: Polynomial χ-binding functions and forbidden in- duced subgraphs: a survey, Graphs Combin. 35 (2019), 1–31. 1

2019
[17]

Randerath, I

B. Randerath, I. Schiermeyer, M. Tewes:3-colorability and Forbidden Subgraphs II: Polynomial Algorithms, Discrete Math. 251 (2002), 137–153. 1 12

2002
[18]

D. P. Sumner, Subtrees of a graph and chromatic number, in: The Theory and Applications of Graphs, (G. Chartrand, ed.), John Wiley & Sons, New York (1981), 557–576. . 1 13

1981

Pith tools

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

[1] [5]

Brause, P

C. Brause, P. Holub, I. Schiermeyer: On 3-colourability, 4-criticality and induced prisms in claw-free graphs, manuscript 2025. 1, 1, 2

work page 2025

[2] [11]

Hodur, M

N. Hodur, M. Pilśniak, M. Prorok, P. Rzążewski, Finding large k-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs, manuscript arXiv:2504.04984, 2025. 6.2

arXiv 2025

[3] [12]

On the distinguishing chromatic number in hereditary graph classes

N. Hodur, M. Pilśniak, M. Prorok, I. Schiermeyer, On 3-colorability of(bull, H)-free graphs, manuscript arXiv:2505.17193, 2025. 1, 3

work page Pith review arXiv 2025

[4] [4]

Brause, P

C. Brause, P. Holub, A. Kabela, Z. Ryjáček, I. Schiermeyer, P. Vrána: On forbidden induced subgraphs for claw-free perfect graphs, Discrete Math. 342 (2019), 1602–

work page 2019

[5] [1]

Ben Rebea: Étude des stables dans les graphes quasi-adjoints (Thèse) Université de Grenoble, France (1981)

A. Ben Rebea: Étude des stables dans les graphes quasi-adjoints (Thèse) Université de Grenoble, France (1981). 12

work page 1981

[6] [2]

J. A. Bondy, U.S.R. Murty: Graph Theory. Springer, 2008. 1

work page 2008

[7] [3]

Brause, T

C. Brause, T. Doan, P. Holub, A. Kabela, Z. Ryjáček, I. Schiermeyer, P. Vrána: Forbidden induced subgraphs and perfectness forK1,3-free perfect graphs of inde- pendence number at least 4, Discrete Math. 345/6, (2022), 112837. 1

work page 2022

[8] [6]

Bruce, C.T

D. Bruce, C.T. Hoàng, J. Sawada: A Certifying Algorithm for3-Colorability of P5- free Graphs, Algorithms and Computation. ISAAC2009. Lecture Notes in Computer Science, 5878 (2009) 594-604

work page 2009