A graph G is said to be 2-divisible if for all (nonempty) induced subgraphs H of G, V(H) can be partitioned into two sets A,B such that ω(A) < ω(H) and ω(B) < ω(H). (Here ω(G) 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, V(H) can be partitioned into two sets A, B such that H][A] is perfect and ω(B) < ω(H). We prove that if a graph is (P5, C5) -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.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- graph coloring
- perfect divisibility