Hadwiger numbers and over-dominating colourings

Thomas Böhme, Alexandr Kostochka, Andrew Thomason

Research output: Contribution to journalArticle

Abstract

Motivated by Hadwiger's conjecture, we say that a colouring of a graph is over-dominating if every vertex is joined to a vertex of each other colour and if, for each pair of colour classes C1 and C2, either C1 has a vertex adjacent to all vertices in C2 or C2 has a vertex adjacent to all vertices in C1. We show that a graph that has an over-dominating colouring with k colours has a complete minor of order at least 2k3 and that this bound is essentially best possible.

Original languageEnglish (US)
Pages (from-to)2662-2665
Number of pages4
JournalDiscrete Mathematics
Volume310
Issue number20
DOIs
StatePublished - Oct 28 2010

Keywords

  • Hadwiger minor over-dominating

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Hadwiger numbers and over-dominating colourings'. Together they form a unique fingerprint.

  • Cite this