Defective Colouring of Graphs Excluding A Subgraph or Minor

Patrice Ossona De Mendez, Sang Il Oum, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

Abstract

Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no Kt+1-minor can be t-coloured so that each colour class induces a subgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness (with relevance to the earth-moon problem), graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor.

Original languageEnglish
Pages (from-to)377-410
Number of pages34
JournalCombinatorica
Volume39
Issue number2
DOIs
Publication statusPublished - 2019

Cite this