pith. sign in

arxiv: 2604.27594 · v2 · pith:CLO3G6A6new · submitted 2026-04-30 · 🧮 math.CO

Structural description of (bull, house)-free graphs

Manoj Belavadi , Chinh T. Hoang This is my paper

Pith reviewed 2026-05-21 00:59 UTC · model grok-4.3

classification 🧮 math.CO
keywords bull-free graphsP5-free graphshouse-free graphsk-critical graphsstructural graph theoryperfect divisibilityinduced-subgraph-free classeschromatic number
0
0 comments X

The pith

(bull, P5)-free graphs have a structure that makes the number of k-critical members finite for every fixed k.

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

The paper supplies a structural description of graphs that contain neither a bull nor a house as an induced subgraph and extends the same approach to (bull, P5)-free graphs. From this description it follows directly that, for any fixed k, only finitely many k-critical graphs can exist inside the (bull, P5)-free class. The same structure also yields a short proof that every (P5, bull)-free graph is perfectly divisible, i.e., the vertices of any induced subgraph with at least one edge can be bipartitioned so that each part meets every largest clique. The finiteness result strengthens an earlier theorem that left the question open for this particular forbidden-pair class.

Core claim

We give a structural description of (bull, house)-free graphs and also (bull, P5)-free graphs. Using these structural properties we prove that for any fixed k, the number of k-critical (bull, P5)-free graphs is finite. This improves on a result of Huang, Li and Xia. Our structural result allows us to give a short proof that (P5, bull)-free graphs are perfectly divisible.

What carries the argument

The structural description that classifies all members of the (bull, house)-free and (bull, P5)-free classes.

If this is right

  • For every fixed k the class of (bull, P5)-free graphs contains only finitely many k-critical members.
  • The same structure immediately yields a short proof of perfect divisibility for all (P5, bull)-free graphs.
  • The finiteness conclusion strengthens the earlier result of Huang, Li and Xia on the same class.

Where Pith is reading between the lines

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

  • The restricted structure may allow polynomial-time coloring algorithms for (bull, P5)-free graphs.
  • Analogous structural arguments could be tried for other pairs of forbidden induced subgraphs to obtain similar finiteness statements.
  • Perfect divisibility may imply further partition or coloring properties not stated in the paper.

Load-bearing premise

The structural description correctly and exhaustively identifies every graph in the (bull, P5)-free class.

What would settle it

An explicit infinite family of pairwise non-isomorphic k-critical (bull, P5)-free graphs for some fixed k would disprove the finiteness claim.

Figures

Figures reproduced from arXiv: 2604.27594 by Chinh T. Hoang, Manoj Belavadi.

Figure 1
Figure 1. Figure 1: Bull, Chair and Gem structure of the complements of P5-free graphs. A house is the complement of the P5. A triangle is the clique on three vertices. Theorem 1.3. Let G be a connected (bull, house)-free graph, then (i) G contains a homogeneous set, or (ii) G is triangle-free, or (iii) G is co-bipartite. Karthick, Maffray, and Pastor [21] proved the following Theorem 1.4 (Theorem 5.2 in [21]). Let G be a con… view at source ↗
Figure 2
Figure 2. Figure 2: The domino and A3 = {v ∈ V (G)|N(v) ∩ X = {x2, x3, x4} or N(v) ∩ X = {x2, x4}}. Note that x2 ∈ A2 and x3 ∈ A3. We may assume there is a vertex y ∈ A2 such that yx2 ∈ E(G). Let B induce the component in G[A2] that contains the edge yx2. We claim that B is a homogeneous set. Suppose not, there exist adjacent vertices b1, b2 in B such that there exists a vertex z /∈ B adjacent to b2 but not to b1. If z is not… view at source ↗
read the original abstract

The bull is a graph consisting of a triangle and two pendant edges. The P_5 is the chordless path on five vertices. The house is the complement of a P_5. A graph is k-critical if it is k-chromatic but each of its proper induced subgraphs is (k-1)-colorable. It is known that the number of k-critical P_5-free graphs and bull-free graphs are infinite for large enough k. We give a structural description of (bull, house)-free graphs and also (bull, P_5)-free graphs. Using these structural properties we prove that for any fixed k, the number of k-critical (bull, P_5)-free graphs is finite. This improves on a result of Huang, Li and Xia (Critical (P_5, bull)-free graphs, Discrete Applied Mathematics 334 (2023) 15-25). A graph G is perfectly divisible if for each induced subgraph H of G with at least one edge, V(H) can be partitioned into two sets V_1, V_2 such that every largest clique of H contains a vertex in V_i for i = 1,2. Chudnovsky and Sivaraman proved that (P_5, bull)-free graphs are perfectly divisible (Perfect divisibility and 2-divisibility, Journal of Graph Theory 90 (2019) 54-60). Our structural result allows us to give a short proof of this theorem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript provides structural descriptions of both (bull, house)-free graphs and (bull, P5)-free graphs. It uses the latter description to prove that, for any fixed k, only finitely many k-critical (bull, P5)-free graphs exist. This improves the earlier result of Huang, Li and Xia. As a byproduct, the structural result yields a short proof that (P5, bull)-free graphs are perfectly divisible.

Significance. The finiteness result for k-critical graphs is significant because the separate P5-free and bull-free classes each contain infinitely many k-critical graphs for sufficiently large k. An explicit structural decomposition that directly implies the finiteness therefore strengthens the literature on chromatic properties of hereditary classes. The alternative short proof of perfect divisibility is a useful contribution. The result would be solid provided the classification is exhaustive.

major comments (2)
  1. §3 (structural description of (bull, P5)-free graphs): the exhaustiveness of the enumerated families is load-bearing for the finiteness claim in Theorem 4.1. An omitted family could in principle contain arbitrarily large k-critical members, as occurs separately in the P5-free and bull-free classes. The manuscript should include an explicit argument or case analysis showing that every (bull, P5)-free graph falls into one of the listed structural classes.
  2. §4.1 (proof of finiteness): the deduction that each listed structural class admits only finitely many k-critical graphs is stated but not expanded; a brief verification for the largest or most complex class would confirm that no hidden infinite families remain inside the decomposition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the structural results and their consequences for critical graphs. We address each major comment below and have revised the manuscript to strengthen the explicitness of the arguments.

read point-by-point responses

  1. Referee: §3 (structural description of (bull, P5)-free graphs): the exhaustiveness of the enumerated families is load-bearing for the finiteness claim in Theorem 4.1. An omitted family could in principle contain arbitrarily large k-critical members, as occurs separately in the P5-free and bull-free classes. The manuscript should include an explicit argument or case analysis showing that every (bull, P5)-free graph falls into one of the listed structural classes.

    Authors: We agree that an explicit demonstration of exhaustiveness is necessary to support the finiteness result. In the revised manuscript we have expanded the proof of the structural theorem in Section 3 with a dedicated case analysis. The argument proceeds by fixing a maximal clique or an induced P5-free subgraph and then examining the possible neighborhoods of vertices outside it; each case is shown to force the graph into one of the enumerated families (e.g., clique joins, bounded-treewidth graphs, or specific modular decompositions) using the absence of bulls and P5s. This case division is now written out in full rather than left implicit. revision: yes

  2. Referee: §4.1 (proof of finiteness): the deduction that each listed structural class admits only finitely many k-critical graphs is stated but not expanded; a brief verification for the largest or most complex class would confirm that no hidden infinite families remain inside the decomposition.

    Authors: We have added a short verification paragraph in Section 4.1 for the most complex class (the one obtained by successive clique substitutions into a base graph of bounded chromatic number). In this class every k-critical member must contain a k-clique and, by the structural restrictions, cannot contain an induced subgraph that is itself k-critical on more than a bounded number of vertices; consequently only finitely many such graphs exist for fixed k. The same reasoning applies, mutatis mutandis, to the remaining classes, confirming that the decomposition introduces no infinite families of k-critical graphs. revision: yes

Circularity Check

0 steps flagged

No circularity; structural theorem is independently derived

full rationale

The paper states a structural description of (bull, house)-free graphs and (bull, P5)-free graphs, then deduces finiteness of k-critical members for fixed k directly from the enumerated classes. No equations, fitted parameters, or self-referential definitions appear. The cited result of Chudnovsky-Sivaraman on perfect divisibility is reproved as a corollary using the new structure, not assumed as input. The Huang-Li-Xia citation is an improvement target, not a load-bearing premise. Exhaustiveness of the classification is the content of the theorem itself and is not reduced to prior inputs by construction. The derivation chain is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definitions of induced subgraphs, chromatic number, and k-critical graphs; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (1)
  • standard math Standard definitions of graphs, induced subgraphs, chromatic number, and k-critical graphs.
    These are the foundational notions invoked throughout the abstract.

pith-pipeline@v0.9.0 · 5802 in / 1151 out tokens · 236930 ms · 2026-05-21T00:59:10.920249+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Bruce, C

    D. Bruce, C. T. Ho` ang and J. Sawada, A certifying algorithm for 3-colorability ofP 5-free graphs,Lecture Notes In Computer Science5878(2009), 594–604

    work page 2009

  2. [2]

    Q. Cai, J. Goedgebeur , S. Huang, Some results onk-criticalP 5-free graphs,Discrete Applied Mathematics, 334 (2023) 91–100

    work page 2023

  3. [3]

    Cameron, and C

    B. Cameron, and C. T. Ho` ang, Infinite families of k-vertex-critical (P 5, C5)- free graphs,Graphs and Combinatorics(2024) 40-30.https://doi.org/10.1007/ s00373-024-02756-x 10

    work page 2024

  4. [4]

    Masset, R

    M. Chudnovsky and S. Safra, The Erd¨ os–Hajnal conjecture for bull-free graphs,Journal of Combinatorial Theory, Series B98:6 (2008) 1301-1310.https://doi.org/10.1016/j. jctb.2008.02.005

    work page doi:10.1016/j 2008

  5. [5]

    Chudnovsky and V

    M. Chudnovsky and V. Sivaraman, Perfect divisibility and 2-divisibility,J Graph Theory 90 (2019) 54–60.https://doi.org/10.1002/jgt.22367

    work page doi:10.1002/jgt.22367 2019

  6. [6]

    Chudnovsky, N.Robertson, P

    M. Chudnovsky, N.Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph The- orem,Annals of Mathematics, Second Series,164:1 (2006), 51–229.ttps://www.jstor. org/stable/20159988

    work page arXiv 2006

  7. [7]

    Chv´ atal, C

    V. Chv´ atal, C. T. Ho` ang, N. V. R. Mahadev and D. De Werra, Four classes of perfectly orderable graphs,J. Graph Theory11:4 (1987), 481–495

    work page 1987

  8. [8]

    H. S. Dhaliwala, A. M. Hamel, C. T. Ho` ang, FM affray, T.J. D. McConnell, S. A. Panait, On color-critical (P 5,co-P5)-free graphs,Discrete Applied Mathematics216 (2017), 142– 148.http://dx.doi.org/10.1016/j.dam.2016.05.018

    work page doi:10.1016/j.dam.2016.05.018 2017

  9. [9]

    Erd˝ os and A

    P. Erd˝ os and A. Hajnal, Ramsey-type theorems,Discrete Appl. Math.25 (1989), 37-52

    work page 1989

  10. [10]

    Gallai, Tibor (1967)

    T. Gallai, Tibor (1967). ”Transitiv orientierbare Graphen”. Acta Mathematica Academiae Scientiarum Hungaricae. 18 (1967) 25–66.https://link.springer.com/article/10. 1007/BF02020961

    work page 1967

  11. [11]

    C. T. Ho` ang, On the structure of perfectly divisible graphs,Discrete Mathematics349 (2026):2.https://doi.org/10.1016/j.disc.2025.114809

    work page doi:10.1016/j.disc.2025.114809 2026

  12. [12]

    C. T. Ho` ang, On the structure of (banner, odd hole)-free graphsJ. Graph Theory, 89 (4) (2018), pp. 395-412

    work page 2018

  13. [13]

    C. T. Ho` ang, B. Moore, D. Recoskie and J. Sawada, Onk-criticalP 5-free graphs, Pro- ceedings of the VII Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 2013),Electronic notes in Discrete Mathematics44 (2013) 187–193

    work page 2013

  14. [14]

    C. T. Ho` ang, M. Kami´ nski, V. Lozin, J. Sawada and X. Shu, A note onk-colourability of P5-free graphs,Lecture Notes in Computer Science5162 (2008) 387–394

    work page 2008

  15. [15]

    Ho` ang, M

    C.T. Ho` ang, M. Kami´ nski, V.V. Lozin, J. Sawada and X. Shu, Decidingk-colorability of P5-free graphs in polynomial time,Algorithmica57:1 (2010) 74–81

    work page 2010

  16. [16]

    Ho` ang and N

    C.T. Ho` ang and N. Khouzam, On brittle graphsJ. Graph Theory12 (1988): 391-404. https://doi.org/10.1002/jgt.3190120310

    work page doi:10.1002/jgt.3190120310 1988

  17. [17]

    Ho` ang and D

    C.T. Ho` ang and D. A. Lazzarato, Polynomial-time algorithms for minimum weighted col- orings of (P5, P 5)-free graphs and related graph classes,Discrete Applied Mathematics186 (2015) 106-111.https://doi.org/10.1016/j.dam.2015.01.022

    work page doi:10.1016/j.dam.2015.01.022 2015

  18. [18]

    C. T. Ho` ang, B. Moore, D. Recoskie, J. Sawada. Constructions ofk-criticalP 5-free graphs. Discrete Applied Mathematics182 (2015), 91–98

    work page 2015

  19. [19]

    Huang, Z

    S. Huang, Z. Li, Vertex-critical (P 5, chair)-free graphs,Discrete Applied Mathematics, 341 (2023) 9–15

    work page 2023

  20. [20]

    Huang, J

    S. Huang, J. Li, W. Xia, Critical (P 5, bull)-free graphs,Discrete Applied Mathematics334 (2023) 15–25

    work page 2023

  21. [21]

    Karthick, F

    T. Karthick, F. Maffray, L. Pastor, Polynomial cases for the vertex coloring problem, Algorithmica, 81(3) (2019) 1053–1074. 11

    work page 2019

  22. [22]

    Kratochv´ ıl, D

    J. Kratochv´ ıl, D. Kr´ al, Zs. Tuza and G.J. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs,Lecture Notes in Computer Science2204 (2001) 254–262

    work page 2001

  23. [23]

    Maffray, and M

    F. Maffray, and M. Preissmann, A translation of Tibor Gallai’s paper: Transitiv orientier- bare Graphen. In: Perfect graphs, J.L. Ramirez-Alfonsin and B.A. Reed Eds., J. Wiley (2001), 25-66

    work page 2001

  24. [24]

    Y. Ju, J. Jooken, J. Goedgebeur, and S. Huang, There Are Finitely Many 5-Vertex-Critical (P6-bull)-Free Graphs,Journal of Graph Theory(2026).https://doi.org/10.1002/jgt. 70027 12

    work page doi:10.1002/jgt 2026