Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree

Abstract

The clustering of a graph coloring is the maximum size of monochromatic components. This paper studies colorings with bounded clustering in graph classes with bounded layered treewidth, which include planar graphs, graphs of bounded Euler genus, graphs embeddable on a fixed surface with a bounded number of crossings per edge, map graphs, amongst other examples. Our main theorem says that every graph with layered treewidth at most $k$ and with maximum degree at most $\Delta$ is $3$-colorable with clustering $O(k^{19}{\Delta }^{37})$. This is the first known polynomial bound on the clustering. This greatly improves upon a corresponding result of Esperet and Joret for graphs of bounded genus.

arXiv commentThis paper is extracted from arXiv:1905.08969. The corresponding part in arXiv:1905.08969 will be deleted

References in corpus (15)

• Layered Separators in Minor-Closed Graph Classes with Applications
• Improper Colourings inspired by Hadwiger's Conjecture
• Coloring planar graphs with three colors and no large monochromatic components
• Islands in minor-closed classes. I. Bounded treewidth and separators
• Clustered 3-Colouring Graphs of Bounded Degree
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Defective and Clustered Choosability of Sparse Graphs
• Clustered Colouring in Minor-Closed Classes
• Clustered Graph Coloring and Layered Treewidth
• Islands in graphs on surfaces
• Improper coloring of graphs with no odd clique minor
• Improper coloring of graphs on surfaces
• Asymptotic dimension of minor-closed families and beyond
• Orthogonal Tree Decompositions of Graphs
• Immersion and clustered coloring

Cited by in corpus (3)

• Colouring Strong Products
• Assouad-Nagata dimension of minor-closed metrics
• Weak diameter choosability of graphs with an excluded minor