Article ID Journal Published Year Pages File Type
4648881 Discrete Mathematics 2010 4 Pages PDF
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 C1C1 and C2C2, either C1C1 has a vertex adjacent to all vertices in C2C2 or C2C2 has a vertex adjacent to all vertices in C1C1.We show that a graph that has an over-dominating colouring with kk colours has a complete minor of order at least 2k/32k/3 and that this bound is essentially best possible.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,