2025/07/24 by Chen, Lizhong, Wang, Hongyang
#05C15 #05C17 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.18506
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 ω(G[B]) < ω(G). We call G perfectly divisible if every induced subgraph of G admits a perfect division. We prove that every (P2 ∪ P4, bull)-free graph G with ω(G) ≥ 3 has a perfect division if G contains no homogeneous set. The clique-number condition is tight: a counterexample exists for ω(G) = 2. Additionally, we present a short proof of the perfect divisibility of (P5, bull)-free graphs, originally established by Chudnovsky and Sivaraman [J. Graph Theory 90 (2019), 54-60.].