Minors in graphs with high chromatic number

Thomas Böhme, Alexandr Kostochka, Andrew Thomason

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)513-518
Number of pages6
JournalCombinatorics Probability and Computing
Volume20
Issue number4
DOIs
StatePublished - Jul 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Minors in graphs with high chromatic number'. Together they form a unique fingerprint.

Cite this