### 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 language | English (US) |
---|---|

Pages (from-to) | 2662-2665 |

Number of pages | 4 |

Journal | Discrete Mathematics |

Volume | 310 |

Issue number | 20 |

DOIs | |

State | Published - 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

Böhme, T., Kostochka, A., & Thomason, A. (2010). Hadwiger numbers and over-dominating colourings.

*Discrete Mathematics*,*310*(20), 2662-2665. https://doi.org/10.1016/j.disc.2010.03.024