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

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