TY - JOUR
T1 - Clustered coloring of graphs with bounded layered treewidth and bounded degree
AU - Liu, Chun Hung
AU - Wood, David R.
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation, United States under Grant No. DMS-1664593, DMS-1929851, DMS-1954054 and DMS-2144042.Partially supported by National Science Foundation, United States under award No. DMS-1664593, DMS-1929851 and DMS-1954054 and CAREER award DMS-2144042.Research supported by the Australian Research Council, Australia.
Funding Information:
This material is based upon work supported by the National Science Foundation, United States under Grant No. DMS-1664593 , DMS-1929851 , DMS-1954054 and DMS-2144042 .
Publisher Copyright:
© 2023 Elsevier Ltd
PY - 2024/12
Y1 - 2024/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85158129162&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2023.103730
DO - 10.1016/j.ejc.2023.103730
M3 - Article
AN - SCOPUS:85158129162
SN - 0195-6698
VL - 122
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103730
ER -