2017/10/07 by Zdenĕk Dvořák, Sergey Norin, Dvořák, Zdeněk +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1710.02727
openalex publication_date 2017/10/07 · openalex created_date 2017/10/20 · openalex updated_date 2026/07/28
The clustered chromatic number of a graph class is the minimum integer t such that for some C the vertices of every graph in the class can be colored in t colors so that every monochromatic component has size at most C. We show that the clustered chromatic number of the class of graphs embeddable on a given surface is four, proving the conjecture of Esperet and Ochem. Additionally, we study the list version of the concept and characterize the minor-closed classes of graphs of bounded treewidth with given clustered list chromatic number. We further strengthen the above results to solve some extremal problems on bootstrap percolation of minor-closed classes.