Islands in graphs on surfaces
Résumé
An island in a graph is a set $X$ of vertices such that each element of $X$ has few neighbors outside $X$. In this paper, we prove several bounds on the size of islands in large graphs embeddable on fixed surfaces. As direct consequences of our results, we obtain the following: (1) Every graph of genus $g$ can be colored from lists of size 5, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 3. (2) Every triangle-free graph of genus $g$ can be colored from lists of size 3, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 10. (3) Every graph of girth at least 6 and genus $g$ can be colored from lists of size 2, in such a way that each monochromatic component has size $O(g)$. Moreover, all but $O(g)$ vertices lie in monochromatic components of size at most 16. While (2) is optimal up to the size of the components, we conjecture that the size of the lists can be decreased to 4 in (1), and the girth can be decreased to 5 in (3). We also study the complexity of minimizing the size of monochromatic components in 2-colorings of planar graphs.