| Autor: |
Chudnovsky, Maria, Fradkin, Alexandra Ovetsky |
| Zdroj: |
Journal of Graph Theory; April 2010, Vol. 63 Issue: 4 p259-278, 20p |
| Abstrakt: |
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 |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
Plný text