Clustered coloring of graphs with bounded layered treewidth and bounded degree

Chun Hung Liu, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

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 layeredtreewidth, 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 Δ is 3-colorable with clustering O(k19Δ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.

Original languageEnglish
Article number103730
Number of pages7
JournalEuropean Journal of Combinatorics
Volume122
DOIs
Publication statusPublished - Dec 2024

Cite this