Perfect Divisions in (P3 ∪ P4, P6,Bull)-Free Graphs

A graph G is said to be perfect if ω(H) = χ(H) for every induced subgraph H of G, where ω(H) and χ(H) denote the clique number and the chromatic number of H. We say that a graph G admits a perfect division if its vertex set can be partitioned into two subsets A and B such that G[A] is perfect and ω(G[B]) < ω(G). If every induced subgraph of G admits a perfect division, then G is called perfectly divisible. A graph P3 ∪ P4 is the disjoint union of paths P3 and P4. A bull refers to the graph consisting of a triangle with two disjoint pendant edges. A homogeneous set X is a proper subset of V(G) with at least two vertices such that every vertex in V(G) \ X is either complete or anticomplete to X. In this paper, we prove that every (P3 ∪ P4, P6, bull)-free graph G with ω(G) ≥ 3 admits a perfect division, provided that G contains no homogeneous set. Moreover, we establish that this clique number condition is tight by presenting a counterexample with clique number exactly 2.