Clustered Graph Coloring and Layered Treewidth

Abstract

A graph coloring has bounded clustering if each monochromatic component has bounded size. This paper studies such a coloring, where the number of colors depends on an excluded complete bipartite subgraph. This is a much weaker assumption than previous works, where typically the number of colors depends on an excluded minor. This paper focuses on 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, amongst other examples. Our main theorem says that for fixed integers $s,t,k$, every graph with layered treewidth at most $k$ and with no $K_{s,t}$ subgraph is $(s+2)$-colorable with bounded clustering. The $s=3$ case implies that every graph with a drawing on a fixed surface with a bounded number of crossings per edge is 5-colorable with bounded clustering. Our main theorem is also a critical component in two companion papers that study clustered coloring of graphs with no $K_{s,t}$ subgraph and excluding a fixed minor, odd minor or topological minor.

The special case for graphs with bounded maximum degree in earlier versions of this paper has been extracted to an individual paper (arXiv:2209.12327) and deleted from this paper

References in corpus (5)

• Layered Separators in Minor-Closed Graph Classes with Applications
• Improper Colourings inspired by Hadwiger's Conjecture
• Defective colouring of graphs excluding a subgraph or minor
• New representation results for planar graphs
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor

Cited by in corpus (11)

• Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
• Clustered 3-Colouring Graphs of Bounded Degree
• Minor-closed graph classes with bounded layered pathwidth
• Clustered Variants of Hajós' Conjecture
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor
• Tree densities in sparse graph classes
• Separating layered treewidth and row treewidth
• Immersion and clustered coloring
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Colouring Strong Products
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three