Name
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 C"1 and C"2, either C"1 has a vertex adjacent to all vertices in C"2 or C"2 has a vertex adjacent to all vertices in C"1. We show that a graph that has an over-dominating colouring with k colours has a complete minor of order at least 2k/3 and that this bound is essentially best possible. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.disc.2010.03.024 | Discrete Mathematics |
Keywords | Field | DocType |
hadwiger minor over-dominating | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Vertex (graph theory),Graph colouring,Neighbourhood (graph theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
310 | 20 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Böhme | 1 | 172 | 21.73 |
| Alexandr Kostochka | 2 | 97 | 13.04 |
| Andrew Thomason | 3 | 71 | 16.01 |