A $4$-color theorem for surfaces of genus $g$

Abstract:

For $\mathcal {G}$ a set of graphs, define the bounded chromatic number ${\chi _B}(\mathcal {G})$ (resp. the bounded path chromatic number ${\chi _p}(\mathcal {G})$) to be the minimum number of colors $c$ for which there exists a constant $M$ such that every graph $G \in \mathcal {G}$ can be vertex $c$-colored so that all but $M$ vertices of $G$ are properly colored (resp. the length of the longest monochromatic path in $G$ is at most $M$). For $\mathcal {G}$ the set of toroidal graphs, Albertson and Stromquist [1] conjectured that the bounded chromatic number is 4. For any fixed $g \geq 0$, let ${\mathcal {S}_g}$ denote the set of graphs of genus $g$. The Albertson-Stromquist conjecture can be extended to the conjecture that ${\chi _B}({\mathcal {S}_g}) = 4$ for all $g \geq 0$. In this paper we show that $4 \leq {\chi _B}({\mathcal {S}_g}) \leq 6$. We also show that the bounded path chromatic number ${\chi _p}({\mathcal {S}_g})$ equals 4 for all $g \geq 0$. Let ${\mu _c}(g,n)({\pi _c}(g,n))$ denote the minimum $l$ such that every graph of genus $g$ on $n$ vertices can be $c$-colored without forcing $l + 1$ monochromatic edges (a monochromatic path of length $l + 1$). We also obtain bounds for ${\mu _c}(g,n)$ and ${\pi _c}(g,n)$.