An approximate version of Hadwiger's conjecture for claw‐free graphs
Maria Chudnovsky, Alexandra Ovetsky Fradkin · Journal of Graph Theory · 2009
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 \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\lceil\frac{2}{3}\chi\rceil$\end{document} . © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 259–278, 2010