pith. sign in

arxiv: 1710.02727 · v1 · pith:EAJAAMWTnew · submitted 2017-10-07 · 🧮 math.CO

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

classification 🧮 math.CO
keywords chromaticclassclassesclusteredminor-closednumberboundedevery
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.