Clustered 3-Colouring Graphs of Bounded Degree

Abstract

A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O({\Delta }^2)$. The previous best bound was $O({\Delta }^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $\Delta$ that exclude a fixed minor are 3-colourable with clustering $O({\Delta }^5)$. The best previous bound for this result was exponential in $\Delta$.

arXiv admin note: text overlap with arXiv:1904.04791

References in corpus (5)

• On Tree-Partition-Width
• Islands in minor-closed classes. I. Bounded treewidth and separators
• Sparse universal graphs for planarity
• Clustered Variants of Hajós' Conjecture
• New representation results for planar graphs

Cited by in corpus (8)

• Adjacency Labelling for Planar Graphs (and Beyond)
• Notes on Graph Product Structure Theory
• Improved product structure for graphs on surfaces
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Product structure extension of the Alon--Seymour--Thomas theorem
• Universality in minor-closed graph classes
• Weak diameter choosability of graphs with an excluded minor
• The grid-minor theorem revisited