Perfect divisibility and 2‐divisibility
Maria Chudnovsky, Vaidy Sivaraman
Source abstract
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 P 5 ‐free, then it is perfectly divisible.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.