Perfect divisibility and 2‐divisibility
Maria Chudnovsky, Vaidy Sivaraman · Journal of Graph Theory · 2018
Abstract A graph G is said to be 2‐divisible if for all (nonempty) induced subgraphs H of G, can be partitioned into two sets such that and . (Here denotes the clique number of G, the number of vertices in a largest clique of G). A graph G is said to be perfectly divisible if for all induced subgraphs H of G, can be partitioned into two sets such that is perfect and . We prove that if a graph is ‐free, then it is 2‐divisible. We also prove that if a graph is bull‐free and either odd‐hole‐free or P5‐free, then it is perfectly divisible.