An approximate version of Hadwiger's conjecture for claw-free graphs
✍ Scribed by Maria Chudnovsky; Alexandra Ovetsky Fradkin
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 189 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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