Perfect divisions in ($P_2 \cup P_4$, bull)-free graphs

Hongyang Wang; Lizhong Chen

REVIEW 1 major objections 5 minor 1 cited by

Perfect divisions in ($P_2 \cup P_4$, bull)-free graphs

T0 review · 1 major / 5 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 (P2∪P4, bull)-free graph with clique number at least 3 either has a homogeneous set or admits a perfect division.

desk verdict A solid, honest extension of the Deng–Chang result to (P2∪P4, bull)-free graphs, with a correct but slightly compressed proof that needs only minor exposition fixes. read the letter →

arxiv 2507.18506 v2 pith:WKOSDIVQ submitted 2025-07-24 math.CO

Lizhong Chen , Hongyang Wang This is my paper · ORCID

classification math.CO MSC 05C1505C1705C69

keywords graphcolouringperfectdivisibilitydivisionbull-freegraphsP2∪P4-freehomogeneoussetcliquenumberchi-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 partitioned into a perfect part and a part whose clique number is strictly smaller. This paper proves that every ($P_2\cup P_4$, bull)-free graph with clique number at least 3 either contains a homogeneous set—a nontrivial vertex set uniformly seen from outside—or admits such a perfect division. The clique-number condition is tight, since a counterexample with clique number 2 exists. The proof chooses a vertex $v$ whose neighbourhood contains a clique of size $\omega(G)-1$ and shows that the induced subgraph on the non-neighbours of $v$ is perfect, yielding the division $\{v\}\cup M(v)$ and $N(v)$. The paper also gives a short proof that ($P_5$, bull)-free graphs are perfectly divisible.

What carries the argument

The load-bearing device is a maximum-degree vertex $v$ selected from the set $A=\{u\in V(G): N(u)\text{ contains a clique of size }\omega(G)-1\}$; the aim is to prove $G[M(v)]$ is perfect, because then $A=\{v\}\cup M(v)$ and $B=N(v)$ form a perfect division. The supporting mechanism is Lemma 2.4: in a bull-free graph with no homogeneous set, if an odd antihole $X$ has $v$ as an anticenter, then every neighbour $x$ of $v$ has at most two neighbours in $X$, and exactly two neighbours only when they are nonadjacent. That restriction, derived from forbidding bulls around $X$, shrinks the possible intersection patterns in the $C_5$, $C_7$, and odd-antihole cases to a handful that are then killed by forced induced $P_2\cup P_4$'s or by degree-maximality contradictions.

What would settle it

Exhaustively search all homogeneous-set-free ($P_2\cup P_4$, bull)-free graphs on up to 11 vertices with clique number 3, and check whether each admits a partition $A,B$ with $G[A]$ perfect and $\omega(G[B])<\omega(G)$; a single graph without such a partition would refute Theorem 1.1.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: if $G$ is a ($P_2\cup P_4$, bull)-free graph with $\omega(G)\ge 3$ and no homogeneous set, then $V(G)$ can be partitioned into sets $A$ and $B$ such that $G[A]$ is perfect and $\omega(G[B])<\omega(G)$. The proof establishes a stronger structural fact: for a vertex $v$ of maximum degree among vertices whose neighbourhood contains a clique of size $\omega(G)-1$, the induced subgraph $G[M(v)]$ is perfect. The argument supposes otherwise and invokes the Strong Perfect Graph Theorem, which forces $G[M(v)]$ to contain an odd antihole of length at least seven, a $C_5$, or a $C_7$; each case is eliminated by exhibiting a forced induced bull or an induced $P_2\cup P_4$, or by contradicting the maximality of $v$'s degree.

Load-bearing premise

The proof depends on the unstated fact that a ($P_2\cup P_4$)-free graph cannot contain an odd hole of length 9 or more, because every such hole contains an induced $P_2\cup P_4$; without that exclusion the case split after the Strong Perfect Graph Theorem is incomplete.

Editorial extensions

If this is right

Every homogeneous-set-free ($P_2\cup P_4$, bull)-free graph with $\omega(G)\ge 3$ admits the explicit partition $A=\{v\}\cup M(v)$, $B=N(v)$ with $G[A]$ perfect and $\omega(B)<\omega(G)$.
The theorem is hereditary on induced subgraphs: any induced subgraph of such a graph that still has clique number at least 3 and no homogeneous set also has a perfect division.
The bound $\omega(G)\ge 3$ cannot be relaxed, because a ($P_2\cup P_4$, bull)-free graph with clique number 2 has no perfect division.
As a corollary of the same techniques, every ($P_5$, bull)-free graph is perfectly divisible, so every induced subgraph of such a graph can be recursively divided.
The result extends the earlier perfect-division theorem for ($P_2\cup P_3$, bull)-free graphs to the next forbidden-path-union case.

Reading between the lines

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

The paper leaves implicit that every odd hole of length at least 9 contains an induced $P_2\cup P_4$; making this one-line observation explicit would make the Strong Perfect Graph Theorem case split fully self-contained.
A natural testable extension is to ($P_2\cup P_k$, bull)-free graphs for larger $k$; the same maximum-degree vertex argument may work as long as the $C_5$, $C_7$, and odd-antihole degenerations can still be forced.
The $\omega=2$ counterexample suggests asking whether every non-perfectly-divisible graph in this class with clique number 2 falls into a finite obstruction list, which would characterise perfect divisibility for the whole class.
An exhaustive computer search over small homogeneous-set-free ($P_2\cup P_4$, bull)-free graphs could test the theorem directly and show whether the maximum-degree choice of $v$ is essential or merely convenient.

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

Dear colleague,

The main theorem generalizes Deng and Chang's 2025 result from (P2∪P3, bull)-free to (P2∪P4, bull)-free graphs: with clique number at least 3, either there is a homogeneous set or a perfect division. The proof follows the established template but adds a nontrivial C7 case, and the structural lemma (Lemma 2.4) is clean. The new short proof of Theorem 1.2, perfect divisibility of (P5, bull)-free graphs, is genuinely shorter and neat. This is honest progress in the bull-free program.

On soundness: I read the case analysis carefully. The stress-test concern about long odd holes is real but minor. After invoking SPGT, the paper lists only odd antiholes, C5, and C7 as obstructions; odd holes of length at least 9 are excluded implicitly because a (P2∪P4)-free graph cannot contain them. That fact is true but never stated, so the case split is not self-contained. One explicit sentence fixes it. The typo in Claim 3 (|N(v)∩C7| should be |N(x)∩C7|) is obvious, and there is also a wrong cross-reference: the C7 section says “By Claim 2” where it means Claim 4. Several “similar analysis” steps in the C7 case and in the new proof of Theorem 1.2 compress the argument, but they are completable and not hiding any real flaw.

The maximum-degree argument in Cases 2 and 3 is the structural heart. It checks out: the choice of v in A, the use of Claim 2/4 to force anticomplete pairs, and the P2∪P4 contradictions all feel right. The clique-number tightness for ω=2 is asserted but not constructed; that is acceptable given the theorem is conditional, though a one-sentence remark or reference would help.

The citation pattern is appropriate. They build on Chudnovsky–Safra, Chudnovsky–Sivaraman, Deng–Chang, and Hu–Xu–Zhuang, and none of the citations appear self-serving or off-point.

Who is this for? Readers working on bull-free graph structure or perfect divisibility. It is a modest but legitimate extension, not a landmark. The paper deserves a serious referee: the theorem is new, the proof is fundamentally sound, and the missing steps are small enough for a referee to fill in. My recommendation is to send it to review, with a request that the authors state the odd-hole exclusion explicitly, fix the typo and the Claim 2/Claim 4 reference, and expand the most compressed “similar analysis” paragraphs.

Referee Report

1 major / 5 minor

Summary. The paper studies perfect divisions in (P2∪P4, bull)-free graphs. Theorem 1.1 asserts that every such graph with clique number at least 3 either contains a homogeneous set or admits a perfect division. The proof selects a vertex v of maximum degree in the set A of vertices whose neighborhoods contain a clique of order ω(G)-1, and shows that G[M(v)] is perfect by contradiction. The contradiction is obtained by applying the Strong Perfect Graph Theorem to an imperfect G[M(v)] and ruling out each possible obstruction using the bull-free and P2∪P4-free conditions. The paper also gives a short proof of the known result that (P5, bull)-free graphs are perfectly divisible.

Significance. If correct, Theorem 1.1 extends the result of Deng and Chang [5] from (P2∪P3, bull)-free graphs to (P2∪P4, bull)-free graphs, a natural step in the study of perfect divisibility and χ-boundedness. The proof is largely self-contained modulo standard external results (SPGT, Chudnovsky–Safra, Hu–Xu–Zhuang) and exhibits a clean maximum-degree-in-A argument. The clique-number condition is shown tight via the Grötzsch graph. The secondary proof of Theorem 1.2 offers a simplification of an existing result, though it relies on the same structural toolkit.

major comments (1)

[Section 3, proof of Theorem 1.1] The case split following the Strong Perfect Graph Theorem is incomplete as stated. The sentence 'By the Strong Perfect Graph Theorem, G[M(v)] contains at least one of the following: an odd antihole of length at least seven, a C5, or a C7' is not justified because SPGT gives an odd hole or an odd antihole, and odd holes of length at least 9 (C9, C11, ...) are not listed. This omission is load-bearing: it defines the three cases on which the whole contradiction proof rests. The missing fact is that for every n≥9, the cycle C_n contains an induced P2∪P4, for example the path v1-v2-v3-v4 together with the edge v6-v7 has no cross edges. Since G is (P2∪P4)-free, these longer odd holes cannot occur; only C5 and C7 remain. This fact should be stated explicitly before the case split; without it, the proof as written is logically incomplete.

minor comments (5)

[Section 3, Claim 3] In Claim 3 and its proof, the neighborhood N(v)∩V(C7) should read N(x)∩V(C7) in several places. For instance, the line 'G is P2∪P4-free implies that |N(v)∩V(C7)|≥3' should refer to x, not v.
[Section 3, Case 3] After Claim 4, the text says 'By Claim 2, we may assume N(x)∩V(C7)=N(y)∩V(C7)'; this should reference Claim 4, not Claim 2.
[Section 2 and Section 3] The set M(v) is defined as V(G)\N(v), so v∈M(v). However, the proof of Theorem 1.1 writes '{v}∪M(v)' as part of the proposed partition, which is redundant unless M(v) is intended to exclude v. Please clarify the definition or the usage.
[Section 4, proof of Theorem 1.2] The statement 'Since G is connected and v can be arbitrary, we may assume that v has a neighbour x such that x has a neighbour in V(X)' needs a brief justification. It is not immediate from connectedness alone that one can choose v and an odd antihole X⊆M(v) with a vertex of N(v) adjacent to X; the proof would benefit from one or two sentences explaining this reduction.
[References] The text of Lemma 2.1 cites 'Hu, Xu and Zhang' but the reference list gives 'Hu, B. Xu, M. Zhuang'. Please make the citation consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proofs rely on external theorems and direct case analysis; the only gap is an unstated but true exclusion of long odd holes, which is a completeness issue, not circularity.

full rationale

The paper's central derivation is not circular. Theorem 1.1 is proved by choosing a vertex v of maximum degree in A (where A consists of vertices whose neighborhood contains a clique of size omega(G)-1) and showing that G[M(v)] is perfect. The proof then constructs a perfect division directly: G[M(v)] is perfect, and N(v) cannot contain a clique of size omega(G) because v is complete to N(v). No fitted parameter, no empirical input, and no conclusion equivalent to an assumption is used. The supporting lemmas are external: the Strong Perfect Graph Theorem [2], the Chudnovsky-Safra bull-free structure lemma [4], and the Hu-Xu-Zhuang result that MNPD graphs have no homogeneous set [8]. None of these is a self-citation by the present authors, and none is assumed in the form of the target theorem. Theorem 1.2 is explicitly credited to Chudnovsky and Sivaraman [3]; the paper offers a new proof, and the proof uses only external theorems and Lemma 2.4, so it is not a renamed or restated input. The only notable gap is that, after invoking the Strong Perfect Graph Theorem in the proof of Theorem 1.1, the case split lists only odd antiholes of length at least seven, C5, and C7, without stating why odd holes of length at least nine are impossible in a (P2 union P4)-free graph. That exclusion is true (for n at least 9, C_n contains an induced P2 union P4), but it is left implicit. This is a proof-completeness or exposition issue, not circularity: the missing fact is an independent graph-theoretic observation, not a restatement of the desired theorem, and adding it would not make the argument self-referential. Therefore the circularity score is 0.

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

The proof is purely combinatorial and introduces no numerical parameters or new entities. The central claim rests on prior structural theorems about bull-free graphs and on the Strong Perfect Graph Theorem, listed as axioms above.

assumptions (4)

standard math Strong Perfect Graph Theorem: a graph is perfect if and only if it contains no odd hole and no odd antihole.
Used in the proofs of Theorem 1.1 and Theorem 1.2 to replace the supposition that G[M(v)] is not perfect by the existence of an odd hole or odd antihole.
domain assumption Lemma 2.1 from Hu, Xu and Zhuang: no minimally non-perfectly divisible graph has a homogeneous set.
Quoted in Section 2 and used to justify working with a graph that contains no homogeneous set.
domain assumption Lemma 2.2 from Chudnovsky and Safra: a bull-free graph with an odd hole or odd antihole that has a center and an anticenter contains a homogeneous set.
Used in Lemma 2.4 and in Case 3 to force contradictions when a vertex is complete to an odd antihole.
standard math Every odd hole of length at least 9 contains an induced P2∪P4, so such holes cannot occur in a (P2∪P4)-free graph.
Implied but not stated in the case split in Section 3; needed to restrict the odd holes coming from the Strong Perfect Graph Theorem to C5 and C7.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Perfect divisions in ($P_2 \cup P_4$, bull)-free graphs." pith.science (2026). https://pith.science/paper/WKOSDIVQ

@misc{pith2026250718506,
  author       = {Pith},
  title        = {Pith review of: Perfect divisions in ($P_2 \cup P_4$, bull)-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WKOSDIVQ}},
  note         = {Machine review of arXiv:2507.18506}
}

abstract

A graph $G$ has a perfect division if its vertex set can be partitioned into two sets $A$, $B$ such that $G[A]$ is perfect and $\omega(G[B]) < \omega(G)$. We call $G$ perfectly divisible if every induced subgraph of $G$ admits a perfect division. We prove that every ($P_2 \cup P_4$, bull)-free graph $G$ with $\omega(G) \geq 3$ has a perfect division if $G$ contains no homogeneous set. The clique-number condition is tight: a counterexample exists for $\omega(G) = 2$. Additionally, we present a short proof of the perfect divisibility of ($P_5$, bull)-free graphs, originally established by Chudnovsky and Sivaraman [J. Graph Theory 90 (2019), 54-60.].

Figures

Figures reproduced from arXiv: 2507.18506 by the authors.

**Figure 1.** Illustration of P2 ∪ P4, bull and banner. induced subgraph of G with vertex set X ⊆ V (G). For two vertex-disjoint graph G1 and G2, the union G1∪G2 is the graph with V (G1∪G2) = V (G1)∪V (G2) and E(G1∪G2) = E(G1)∪E(G2). A clique Kn is a graph on n vertices such that every two vertices of Kn are adjacent. For an integer k ≥ 1, Pk and Ck denote the path on k vertices and the cycle on k vertices, respectively. A path i… view at source ↗

**Figure 2.** Gr¨otzsch graph For the sake of contradiction, suppose G[M(v)] is not perfect. By the Strong Perfect Graph Theorem [2], G[M(v)] contains at least one of the following: an odd antihole of length at least seven, a C5, or a C7. Case 1. G[M(v)] contains an odd antihole X of length at least seven. Let V (X) = {v1, v2, . . . , vn}, and vi ∼ vj if and only if |i − j| ̸= 1 (indices are modulo n). N(v) ̸= ∅ since G is connec… view at source ↗

Review history (2 revisions) →

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

9 extracted references · 9 canonical work pages · cited by 1 Pith paper

[5]

Deng and C

Z. Deng and C. Chang, On the structure of some classes of (P_2 P_3) -free graphs, Graphs Combin. 41 (2025), 63

work page 2025
[1]

A. P. Bharathi and S. A. Choudum, Coloring of (P_3 P_2) -free graphs, Graphs Comb. 34 (2018), 97-107

work page 2018
[2]

Chudnovsky et al., The strong perfect graph theorem, Annal

M. Chudnovsky et al., The strong perfect graph theorem, Annal. Math. 164 (2006), 51–229

work page 2006
[3]

Chudnovsky and V

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

work page 2019
[4]

Chudnovsky and S

M. Chudnovsky and S. Safra, The Erdős-Hajnal Conjecture for bull-free graphs, J. Combin. Theory Ser. B 98 (2008), 1301–1310

work page 2008
[6]

Gy\' a rf\' a s, Problems from the world surrounding perfect graphs, Zastos

A. Gy\' a rf\' a s, Problems from the world surrounding perfect graphs, Zastos. Mat. Appl. Math. 19 (1987), 413–441

work page 1987
[7]

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

work page 2018
[8]

C. T. Ho\`ang, On the structure of perfectly divisible graphs, https://arxiv.org/abs/2506.12660 (2025)

work page Pith review arXiv 2025

Show all 9 references

[9]

Q. Hu, B. Xu, M. Zhuang, Perfect weighted divisibility is equivalent to perfect divisibility, https://arxiv.org/abs/2504.13695 (2025)

2025

Pith tools

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

[1] [5]

Deng and C

Z. Deng and C. Chang, On the structure of some classes of (P_2 P_3) -free graphs, Graphs Combin. 41 (2025), 63

work page 2025

[2] [1]

A. P. Bharathi and S. A. Choudum, Coloring of (P_3 P_2) -free graphs, Graphs Comb. 34 (2018), 97-107

work page 2018

[3] [2]

Chudnovsky et al., The strong perfect graph theorem, Annal

M. Chudnovsky et al., The strong perfect graph theorem, Annal. Math. 164 (2006), 51–229

work page 2006

[4] [3]

Chudnovsky and V

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

work page 2019

[5] [4]

Chudnovsky and S

M. Chudnovsky and S. Safra, The Erdős-Hajnal Conjecture for bull-free graphs, J. Combin. Theory Ser. B 98 (2008), 1301–1310

work page 2008

[6] [6]

Gy\' a rf\' a s, Problems from the world surrounding perfect graphs, Zastos

A. Gy\' a rf\' a s, Problems from the world surrounding perfect graphs, Zastos. Mat. Appl. Math. 19 (1987), 413–441

work page 1987

[7] [7]

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

work page 2018

[8] [8]

C. T. Ho\`ang, On the structure of perfectly divisible graphs, https://arxiv.org/abs/2506.12660 (2025)

work page Pith review arXiv 2025