zbMATH — the first resource for mathematics

A 4-color theorem for surfaces of genus g. (English) Zbl 0672.05028
Authors’ abstract: “For $${\mathcal F}^ a$$set of graphs, define the bounded chromatic number $$\chi_ B({\mathcal F})$$ (resp. the bounded path chromatic numbers $$\chi_ P({\mathcal F}))$$ to be the minimum number of colors c for which there exists a constant M such that every graph $$G\in {\mathcal F}$$ 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 F}$$ the set of toroidal graphs, Albertson and Stromquist 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 $$\ell$$ such that every graph of genus g on n vertices can be c-colored without forcing $$\ell +1$$ monochromatic edges (a monochromatic path of length $$\ell +1)$$. We also obtain bounds for $$\mu_ c(g,n)$$ and $$\pi_ c(g,n).''$$
Reviewer: I.Tomescu

MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: