Pith. sign in

REVIEW 6 minor 23 references

Perfect divisibility and perfect-Pollyanna in bull-free graphs

T0 review · 0 major / 6 minor · reviewed 2026-07-13 · grok-4.5

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

Pith's one-line read Five open perfect-divisibility conjectures all hold for bull-free graphs, and three (bull, H)-free classes are perfect-Pollyanna.

desk verdict Solid case-analysis paper that settles five conjectures inside bull-free graphs and introduces a clean perfect-Pollyanna template; proofs look standard and careful. read the letter →

arxiv 2603.21538 v2 pith:GG7542WX submitted 2026-03-23 math.CO cs.DM

Ran Chen , Paras Vinubhai Maniya , Di Wu , Junran Yu This is my paper · ORCID
classification math.COcs.DM MSC 05C1505C75
keywords perfectdivisibilitybull-freegraphsperfect-Pollyannaoddtorchweight-divisiblehomogeneoussetχ-boundedness
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

A graph is perfectly divisible when every induced subgraph can be split into a perfect piece and a leftover piece whose largest clique is strictly smaller. Five well-known conjectures assert that this property holds for P5-free graphs, odd-hole-free graphs, even-hole-free graphs, 4K1-free graphs, and fork-free graphs. The paper proves that every one of those five statements is true once the extra forbidden subgraph “bull” is added. The proofs proceed by showing that any minimal counter-example that is also bull-free must be triangle-free and therefore already known to be perfectly divisible. In addition, the authors introduce the notion of a perfect-Pollyanna class: a hereditary class C such that the intersection of C with any class whose triangle-free members are 3-colourable remains perfectly divisible. They prove that the three classes of (bull, house)-free, (bull, hammer)-free and (bull, diamond)-free graphs are perfect-Pollyanna, which immediately yields several new infinite families of perfectly divisible graphs.

What carries the argument

The structural dichotomy for bull-free graphs: either a homogeneous set exists, or for every vertex v at least one of the neighbourhood N(v) or the non-neighbourhood M(v) induces a perfect graph. Combined with the fact that minimal non-perfectly-weight-divisible graphs have no homogeneous sets, this forces every candidate counter-example to be locally perfect and triangle-free, after which known colouring results finish the argument.

What would settle it

An explicit bull-free graph that is not perfectly divisible (or a bull-free minimal non-perfectly-weight-divisible graph that contains a triangle and no homogeneous set) would refute the main theorems.

Watch

Extended reading notes

Core claim

Every (bull, odd-torch)-free graph, every (bull, even-hole)-free graph and every (bull, 4K1)-free graph is perfectly weight-divisible; consequently the five listed conjectures hold for bull-free graphs. Moreover the classes of (bull, H)-free graphs for H in {house, hammer, diamond} are perfect-Pollyanna.

Load-bearing premise

The entire case analysis rests on the claim that every bull-free graph either has a homogeneous set or, for every vertex, at least one of its neighbourhood or non-neighbourhood induces a perfect graph.

Editorial extensions

If this is right

  • All five open conjectures of Hoàng and Karthick et al. become true inside the bull-free world.
  • Any hereditary class whose triangle-free members are 3-colourable yields a perfectly divisible class when intersected with (bull, house)-, (bull, hammer)- or (bull, diamond)-free graphs.
  • Concrete new perfectly divisible families include (bull, P11, C4)-free, (bull, P14, C5, C4)-free and (bull, P17, C6, C5, C4)-free graphs.
  • Every (bull, odd-torch)-free or (bull, 4K1)-free graph satisfies χ ≤ ω(ω+1)/2.

Reading between the lines

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

  • The same dichotomy-plus-minimal-counterexample strategy may decide whether the whole class of bull-free graphs is perfect-Pollyanna, the open question left by the authors.
  • If every bull-free minimal non-perfectly-weight-divisible graph is forced to be triangle-free, the five conjectures would hold without any extra forbidden subgraphs.
  • The perfect-Pollyanna property supplies a uniform template for converting 3-colourability results on triangle-free graphs into perfect-divisibility theorems for larger hereditary classes.
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

0 major / 6 minor

Summary. The paper studies perfect divisibility (and the stronger perfect weight-divisibility) for bull-free graphs. It proves that every (bull, odd-torch)-free graph, every (bull, even-hole)-free graph and every (bull, 4K1)-free graph is perfectly weight-divisible (Theorems 2–4), so the five conjectures of Hoàng and of Karthick et al. hold when restricted to bull-free graphs. It further introduces the notion of a perfect-Pollyanna class and shows that the classes of (bull, H)-free graphs for H ∈ {house, hammer, diamond} are perfect-Pollyanna (Theorems 5–6). The arguments proceed by the standard minimal non-perfectly-weight-divisible (MNWD) template: Lemmas 1–2 (homogeneous-set freeness and the Chudnovsky–Safra dichotomy) force every bull-free MNWD graph to be connected and locally perfect with every M(v) imperfect and free of large odd antiholes; subsequent case analyses around odd holes then produce either a good partition or a forbidden induced subgraph. Corollaries recover earlier results of Chudnovsky–Sivaraman and Karthick et al. and yield new perfect-divisibility statements for several (bull, path/cycle)-free classes.

Significance. The results give a uniform positive answer to five open conjectures inside the bull-free world and introduce a clean “perfect-Pollyanna” framework that reduces perfect divisibility of (bull, H)-free graphs to the triangle-free case. The proofs are self-contained once the Chudnovsky–Safra dichotomy and the Strong Perfect Graph Theorem are granted, and they systematically strengthen earlier partial results. The work therefore advances both the structural theory of bull-free graphs and the programme of identifying hereditary classes that are perfectly divisible.

minor comments (6)
  1. Title of the arXiv version (“Perfect divisibility of some bull-free graphs and its application”) differs slightly from the abstract title; unify for the final version.
  2. Figure 1 caption and the list of forbidden subgraphs would benefit from a short explicit definition of “odd torch on a 5-hole” already in the introduction, rather than only in the figure.
  3. In the proof of Lemma 5 the phrase “H = v1v2···vkv1 is an odd hole” is slightly confusing because H is introduced as an antihole; a parenthetical remark that the complement is the hole would help.
  4. Claim numbering restarts in each section; a global numbering or section-prefixed labels would make cross-references easier.
  5. A few typographical slips remain (e.g., “appli cation”, “fiv e”, “Ho` ang” spacing, “geneality”). A careful copy-edit will remove them.
  6. The final open problems (Problems 1–2) are well-motivated; a one-sentence remark on why the diamond case of Theorem 7 does not immediately settle Problem 2 would be useful for the reader.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; independent structural case analyses on MNWD bull-free graphs build on external theorems without reducing claims to inputs by construction.

full rationale

The paper's core claims (Theorems 2-4 on perfect weight-divisibility of (bull, odd-torch)-free, (bull, even-hole)-free and (bull, 4K1)-free graphs; Theorems 5-6/8 on perfect-Pollyanna for (bull, H)-free with H in {house, hammer, diamond}) are established via standard MNWD minimality arguments: assume a counterexample G, invoke external Lemma 1 (no homogeneous sets in MNWD graphs, from Chudnovsky-Sivaraman) and Lemma 2 (bull-free dichotomy: homogeneous set or N(v)/M(v) perfect, from Chudnovsky-Safra), deduce local perfection and presence of odd holes in every M(v) (Lemmas 5-6, using SPGT), then perform exhaustive case analyses on neighborhoods relative to the hole (Claims 1-14, Lemmas 7-11) that produce either a good partition or a forbidden induced subgraph. These cases are self-contained combinatorial arguments, not equivalent by definition to the inputs. Supporting results (Lemma 3 on triangle-free equivalence, Lemma 4/Theorem 7 from Chen-Xu on diamond-free structure, Lemma 9 on even-hole chi-bounds) are either elementary or externally cited; self-citations ([5],[6]) appear only for background corollaries or related coloring bounds and are not load-bearing for the new partitions. No self-definitional loops, fitted parameters, uniqueness smuggling, or renaming of known results occur. The five conjectures are shown only for the bull-free restriction, which is a genuine specialization rather than a circular restatement.

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

Pure mathematics paper. No free parameters or fitted constants. Background axioms are standard graph-theoretic facts and previously published structural theorems. The only new conceptual entity is the definition of perfect-Pollyanna, which is introduced by definition rather than postulated as an unobserved object.

assumptions (5)
  • standard math Strong Perfect Graph Theorem: a graph is perfect iff it is (odd-hole, odd-antihole)-free
    Invoked repeatedly to recognise perfect induced subgraphs (Theorem 1, used in Lemmas 5–6, Claims 10–13, etc.).
  • domain assumption Every MNWD graph has no homogeneous set (Lemma 1, cited from Chudnovsky–Sivaraman)
    Used as the starting point for all structural arguments about minimal counter-examples.
  • domain assumption Bull-free dichotomy: either a homogeneous set exists or for every v at least one of N(v), M(v) is perfect (Lemma 2, cited from Chudnovsky–Safra)
    Load-bearing structural fact that forces local perfection of MNWD bull-free graphs.
  • domain assumption Even-hole-free graphs satisfy χ ≤ 2ω−1 (Lemma 9, cited from Chudnovsky–Seymour)
    Used only for the even-hole case (Theorem 3) to obtain 3-colourability of triangle-free members.
  • domain assumption Triangle-free graphs are perfectly divisible iff χ ≤ 3 (Hoàng)
    Converts the perfect-Pollyanna statements into colouring statements (Lemma 3, Theorem 6).
invented entities (1)
  • perfect-Pollyanna class
    purpose: Captures the property that intersection with any hereditary class whose triangle-free members are 3-colourable automatically yields perfect divisibility
    Defined in the introduction and used to organise Theorems 5–6 and the corollaries; purely definitional, no independent physical or combinatorial existence claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Perfect divisibility and perfect-Pollyanna in bull-free graphs." pith.science (2026). https://pith.science/paper/GG7542WX

@misc{pith2026260321538,
  author       = {Pith},
  title        = {Pith review of: Perfect divisibility and perfect-Pollyanna in bull-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GG7542WX}},
  note         = {Machine review of arXiv:2603.21538}
}
abstract

A graph $G$ is {\em perfectly divisible} if, for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B])<\omega(H)$. A {\em bull} is a graph consisting of a triangle with two disjoint pendant edges. Ho\`ang [Discrete Math. 349 (2026) 114809] proposed four conjectures: 1. $P_5$-free graphs are perfectly divisible; 2. Odd hole-free graphs are perfectly divisible; 3. Even hole-free graphs are perfectly divisible; and 4. $4K_1$-free graphs are perfectly divisible. Karthick et al. [Electron. J. Combin. 29 (2022) P3.19] proposed a conjecture: Fork-free graphs are perfectly divisible. In this paper, we prove that all of five conjectures above hold for bull-free graphs. Our results also generalize some results of Chudnovsky and Sivaraman [J. Graph Theory 90 (2019) 54--60] and Karthick et al. [Electron. J. Combin. 29 (2022) P3.19]. We say that a class ${\cal C}$ is {\em perfect-Pollyanna} if ${\cal C}\cap {\cal G}$ is perfectly divisible for any hereditary class ${\cal G}$ in which each triangle-free graph is 3-colorable. Let $H\in\{\text{house, hammer, diamond}\}$. In this paper, we prove that the class of $(\text{bull}, H)$-free graphs is perfect-Pollyanna. Let ${\cal C}$ be the class of $(\text{bull}, H)$-free graphs. This implies that ${\cal C}\cap {\cal G}$ is perfectly divisible if and only if all of triangle-free graphs in ${\cal G}$ are perfectly divisible. As corollaries, we show that $(\text{bull},{\cal H})$-free graphs are perfectly divisible, where ${\cal H}$ is one of $\{P_{11},C_4\},\{P_{14},C_5,C_4\}$, and $\{P_{17},C_6,C_5,C_4\}$.

Figures

Figures reproduced from arXiv: 2603.21538 by the authors.

Figure 1
Figure 1. Illustration of some small graphs. A bull is a graph consisting of a triangle with two disjoint pendant edges. A house is the complement of P5, a hammer is a graph obtained by identifying an end vertex of a P3 with a vertex of a triangle. A diamond is a graph consisting of two triangles sharing exactly one common edge. A fork is a graph obtained from K1,3 by subdividing an edge once. An E is a graph obtained from an… view at source ↗
Figure 2
Figure 2. Illustration of F, and the partition of V (G): the red sets belong to A and the blue sets belong to B. Claim 11. X2 is anticomplete to Z \ Z2 and complete to Z2. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 2 linked inside Pith

  1. [1]

    J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, New Yo rk, 2008

    2008

  2. [2]

    Brause, M

    C. Brause, M. Geißer, I. Schiermeyer, Homogeneous sets, clique-separators, critical graphs, and optimal χ -binding functions, Discrete Appl. Math. 320 (2022) 211–22 2

    2022

  3. [3]

    Bria´ nski, J

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

    2024

  4. [4]

    L. Chen, H. Wang, Perfect division in ( P2 ∪ P4, bull)-free graphs, arXiv:2507.18506v2.(2025)

    arXiv 2025

  5. [5]

    R. Chen, B. Xu, Structure and linear-Pollyanna of some sq uare-free graphs, Discrete Math. 349 (2026) 114979

    2026

  6. [6]

    R. Chen, B. Xu, Structure and coloring of ( P7, C 5, diamond)-free graphs, Discrete Appl. Math. 372 (2025) 298–307

    2025

  7. [7]

    Chudnovsky, L

    M. Chudnovsky, L. Cook, J. Davies, S. Oum, Reuniting χ -boundedness with polynomial χ - boundedness, J. Combin. Theory Ser. B 176 (2026) 30–73. 16

    2026

  8. [8]

    Chudnovsky, N

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

    2006

Show all 23 references
  1. [9]

    Chudnovsky, S

    M. Chudnovsky, S. Safra, The Erd˝ os-Hajnal conjecture f or bull-free graphs. J. Combin. Theory Ser. B 98 (2008) 1301–1310

    2008

  2. [10]

    Chudnovsky, P

    M. Chudnovsky, P. Seymour, Even-hole-free graphs stil l have bisimplicial vertices, J. Combin. Theory B 161 (2023) 331–381

    2023

  3. [11]

    Chudnovsky, V

    M. Chudnovsky, V. Sivaraman, Perfect divisibility and 2-divisibility, J. Graph Theory 90 (2019) 54–60

    2019

  4. [12]

    Z. Deng, C. Chang, On the structure of some classes of ( P2 ∪ P3)-free graphs, Graphs Combin. 41 (2025) 63

    2025

  5. [13]

    Erd˝ os, Graph theory and probability, Canad

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

    1959

  6. [14]

    Esperet, Graph colorings, flows and perfect matching s, Habilitation Thesis, Universit´ e Greno- ble Alpes, 2017

    L. Esperet, Graph colorings, flows and perfect matching s, Habilitation Thesis, Universit´ e Greno- ble Alpes, 2017

    2017

  7. [15]

    Goedgebeur, O

    J. Goedgebeur, O. Schaudt, Exhaustive generation of k-critical H-free graphs, J. Graph Theory 87 (2018) 188–207

    2018

  8. [16]

    C. T. Ho` ang, On the structure of (banner, odd hole)-fre e graphs, J. Graph Theory 89 (2018) 395–412

    2018

  9. [17]

    C. T. Ho` ang, On the structure of perfectly divisible gr aphs, Discrete Math. 349 (2026) 114809

    2026

  10. [18]

    Hodur, M

    N. Hodur, M. Pil´ sniak, M. Prorok, I. Schiermeyer, On k-colorability of (bull, H)-free graphs, arXiv:2509.01698v1 (2025)

    2025 arXiv

  11. [19]

    Gy´ arf´ as, On Ramsey covering-numbers, Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P

    A. Gy´ arf´ as, On Ramsey covering-numbers, Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erd˝ os on his 60th birthday), Vol. II, Colloq . Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam, pp. 801–816 (1975)

    1973

  12. [20]

    Karthick, J

    T. Karthick, J. Kaufmann, V. Sivaraman, Coloring graph classes with no induced fork via perfect divisibility, Electron. J. Combin. 29 (2022) P3.19

    2022

  13. [21]

    Lov´ asz, Normal hypergraphs and the perfect graph co njecture, Discrete Math

    L. Lov´ asz, Normal hypergraphs and the perfect graph co njecture, Discrete Math. 2 (3) (1972) 253–267

    1972

  14. [22]

    Schiermeyer, B

    I. Schiermeyer, B. Randerath, Polynomial χ -binding functions and forbidden induced sub- graphs: A survey, Graphs Combin. 35 (2019) 1–31

    2019

  15. [23]

    D. Wu, B. Xu, Perfect divisibility and coloring of some f ork-free graphs, Discrete Math. 347 (2024) 114121. 17

    2024

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.