Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 54-60 |
Number of pages | 7 |
Journal | Journal of Graph Theory |
Volume | 90 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2019 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- 2-divisibility
- graph coloring
- perfect divisibility