Pith. sign in

Islands in minor-closed classes. I. Bounded treewidth and separators

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

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.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2025 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

unclear 1

representative citing papers

3-Colouring Planar Graphs

math.CO · 2025-07-03 · conditional · novelty 7.0

Every n-vertex planar graph can be 3-coloured so that each monochromatic connected component has at most O(n^{4/9}) vertices, improving the previous O(n^{1/2}) bound.

citing papers explorer

Showing 1 of 1 citing paper.

  • 3-Colouring Planar Graphs math.CO · 2025-07-03 · conditional · none · ref 12 · internal anchor

    Every n-vertex planar graph can be 3-coloured so that each monochromatic connected component has at most O(n^{4/9}) vertices, improving the previous O(n^{1/2}) bound.