Hadwiger's conjecture states that every graph with chromatic number χ has a clique minor of size χ. In this paper we prove a weakened version of this conjecture for the class of claw-free graphs (graphs that do not have a vertex with three pairwise nonadjacent neighbors). Our main result is that a claw-free graph with chromatic number χ has a clique minor of size ⌈2/3χ⌉.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Claw-free graphs
- Clique minors
- Hadwiger's conjecture