An approximate version of Hadwiger's conjecture for claw‐free graphs |
| |
Authors: | Maria Chudnovsky Alexandra Ovetsky Fradkin |
| |
Affiliation: | 1. Columbia University, New York, New York 10027;2. Princeton University, Princeton, New Jersey 08544 |
| |
Abstract: | 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 $lceilfrac{2}{3}chirceil$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 259–278, 2010 |
| |
Keywords: | claw‐free graphs Hadwiger's conjecture coloring clique minors |
|
|