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 commentarXiv admin note: text overlap with arXiv:1904.04791

References in corpus (22)

• Diameter and Treewidth in Minor-Closed Graph Families
• Layered Separators in Minor-Closed Graph Classes with Applications
• On Tree-Partition-Width
• Improper Colourings inspired by Hadwiger's Conjecture
• A relative of Hadwiger's conjecture
• Planar graphs have bounded nonrepetitive chromatic number
• Track Layouts, Layered Path Decompositions, and Leveled Planarity
• Islands in minor-closed classes. I. Bounded treewidth and separators
• Sparse universal graphs for planarity
• Coloring planar graphs with three colors and no large monochromatic components
• Better bounds for poset dimension and boxicity
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Clustered Colouring in Minor-Closed Classes
• Defective and Clustered Choosability of Sparse Graphs
• Clustered Graph Coloring and Layered Treewidth
• Minor-closed graph classes with bounded layered pathwidth
• Clustered Variants of Hajós' Conjecture
• Islands in graphs on surfaces
• New representation results for planar graphs
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor
• Improper coloring of graphs on surfaces
• Improper coloring of graphs with no odd clique minor

Cited by in corpus (9)

• Adjacency Labelling for Planar Graphs (and Beyond)
• Notes on Graph Product Structure Theory
• Minor-closed graph classes with bounded layered pathwidth
• 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