Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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

Authors: Kenneth A. Berman and Jerome L. Paul
Journal: Proc. Amer. Math. Soc. 105 (1989), 513-522
MSC: Primary 05C15
MathSciNet review: 949874
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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)$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C15

Retrieve articles in all journals with MSC: 05C15

Additional Information

Keywords: Vertex coloring, genus $ g$, chromatic number
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society