Defective colouring of graphs excluding a subgraph or minor

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 $K_{t+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.

References in corpus (8)

• Characterisations and Examples of Graph Classes with Bounded Expansion
• A relative of Hadwiger's conjecture
• Disproof of the List Hadwiger Conjecture
• Many, many more intrinsically knotted graphs
• Forcing a sparse minor
• On triangles in K_r-minor free graphs
• The extremal function for Petersen minors
• Book drawings of complete bipartite graphs

Cited by in corpus (15)

• Planar graphs have bounded queue-number
• Improper Colourings inspired by Hadwiger's Conjecture
• Defective and Clustered Choosability of Sparse Graphs
• Clustered Colouring in Minor-Closed Classes
• Clustered Graph Coloring and Layered Treewidth
• Tree densities in sparse graph classes
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor
• Improper coloring of graphs with no odd clique minor
• Homomorphism counts in robustly sparse graphs
• Defective coloring is perfect for minors
• Phase Transition of Degeneracy in Minor-Closed Families
• Defective DP-colorings of sparse multigraphs
• The grid-minor theorem revisited
• Defective DP-colorings of sparse simple graphs
• Colourings with Bounded Monochromatic Components in Graphs of Given Circumference