Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-02-12T01:21:19.275Z Has data issue: false hasContentIssue false
  • English
  • Français

Minors in Graphs with High Chromatic Number

Published online by Cambridge University Press:  13 April 2011

THOMAS BÖHME ,
ALEXANDR KOSTOCHKA  and
ANDREW THOMASON
THOMAS BÖHME
Affiliation:
Institut für Mathematik, Technische Universität Ilmenau, Ilmenau, Germany (e-mail: tboehme@theoinf.tu-ilmenau.de)
ALEXANDR KOSTOCHKA
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA and Sobolev Institute of Mathematics, Novosibirsk, Russia (e-mail: kostochk@math.uiuc.edu)
ANDREW THOMASON
Affiliation:
DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge, UK (e-mail: A.G.Thomason@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We develop lower bounds on the Hadwiger number h(G) of graphs G with high chromatic number. In particular, if G has n vertices and chromatic number k then h(G) ≥ (4k − n)/3.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 4 , July 2011 , pp. 513 - 518
Copyright
Copyright © Cambridge University Press 2011

References

[1]Dirac, G. A. (1964) Homomorphism theorems for graphs. Math. Ann. 153 69–80.CrossRefGoogle Scholar
[2]Duchet, P. and Meyniel, H. (1982) On Hadwiger's number and the stability number. In Graph Theory (Bollobás, B., ed.), Vol. 13 of Annals of Discrete Mathematics, North-Holland, pp. 71–73.Google Scholar
[3]Gallai, T. (1963) Kritische Graphen II. Publ. Math. Inst. Hungar. Acad. Sci. 8 373–395.Google Scholar
[4]Kawarabayashi, K. and Song, Z. (2007) Independence numbers and clique minors. J. Graph Theory 56 219–226.CrossRefGoogle Scholar
[5]Plummer, M. D., Stiebitz, M. and Toft, B. (2003) On a special case of Hadwiger's conjecture. Discussiones Mathematicae Graph Theory 23 333–363.CrossRefGoogle Scholar
[6]Robertson, N., Seymour, P. D. and Thomas, R. (1993) Hadwiger's conjecture for K 6-free graphs. Combinatorica 13 279–362.CrossRefGoogle Scholar
[7]Stehlík, M. (2009) Critical graphs with connected complements. J. Combin. Theory Ser. B 89 189–194.CrossRefGoogle Scholar
[8]Wagner, K. (1937) Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 570–590.CrossRefGoogle Scholar