Perfect divisibility and 2‐divisibility
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 10, 2018
- Source ID
- 10.1002/jgt.22367
Entities
People
- Maria Chudnovsky
- Vaidy Sivaraman
Organizations
- Army Research Office
- Binghamton University
- National Science Foundation Division of Mathematical Sciences
- Princeton University