2025/09/23 by Ran Chen, Chen, Ran, Di Wu +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Finite Group Theory Research
paper · pdf · doi:10.48550/arxiv.2509.18856
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 ω(H[B])<ω(H). A \em bull is a graph consisting of a triangle with two disjoint pendant edges, a \em fork is a graph obtained from K1,3 by subdividing an edge once, and an \em odd torch is a graph obtained from an odd hole by adding an edge xy such that x is non-adjacent to any vertex on the odd hole and the set of neighbors of y on the odd hole is a stable set. Chudnovsky and Sivaraman [J. Graph Theory 90 (2019) 54-60] proved that every (odd hole, bull)-free graph and every (P5, bull)-free graph are perfectly divisible. Karthick \em et al. [The Electron. J. of Combin. 29 (2022) P3.19.] proved that every (fork, bull)-free graph is perfectly divisible. Chen and Xu [Discrete Appl. Math. 372 (2025) 298-307.] proved that every (P7,C5, bull)-free graph is perfectly divisible. Let H∈\\odd~torch\, \P8,C5\\. In this paper, we prove that every (H, bull)-free graph is perfectly divisible. We also prove that a (P6, bull)-free graph is perfectly divisible if and only if it contains no Mycielski-Grötzsch graph as an induced subgraph. As corollaries, these graphs are \binomω+12-colorable. Notice that every odd torch contains an odd hole, an induced P5, and an induced fork. Therefore, our results generalize their findings. Moreover, we prove that every (P6, bull)-free graph G satisfies χ(G)≤ω(G)7.