TY - JOUR

T1 - Hadwiger numbers and over-dominating colourings

AU - Böhme, Thomas

AU - Kostochka, Alexandr

AU - Thomason, Andrew

N1 - Funding Information:
We acknowledge with gratitude the thoughtful remarks of the referees. The research of the second author was supported by NSF grant DMS-0650784 and grant 08-01-00673 of the Russian Foundation for Fundamental Research .

PY - 2010/10/28

Y1 - 2010/10/28

N2 - 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.

AB - 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.

KW - Hadwiger minor over-dominating

UR - http://www.scopus.com/inward/record.url?scp=77955550276&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955550276&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2010.03.024

DO - 10.1016/j.disc.2010.03.024

M3 - Article

AN - SCOPUS:77955550276

VL - 310

SP - 2662

EP - 2665

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 20

ER -