Back to Search Start Over

Clustered coloring of graphs with bounded layered treewidth and bounded degree

Authors :
Liu, Chun-Hung
Wood, David R.
Source :
European Journal of Combinatorics. :103730
Publication Year :
2023
Publisher :
Elsevier BV, 2023.

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.<br />Comment: This paper is extracted from arXiv:1905.08969. The corresponding part in arXiv:1905.08969 will be deleted

Details

ISSN :
01956698
Database :
OpenAIRE
Journal :
European Journal of Combinatorics
Accession number :
edsair.doi.dedup.....6541a60f2d8e3d33e83ad358aaecc0fd
Full Text :
https://doi.org/10.1016/j.ejc.2023.103730