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?)

  • [1] M. Albertson and W. Stromquist, Locally planar toroidal graphs are $ 5$-colorable, Proc. Amer. Math. Soc. 84 (1982), 449-456. MR 640251 (83a:05053)
  • [2] K. Appel and W. Haken, The solution of the four-color map problem, Sci. Amer. 237 (1977), 108-121. MR 0543796 (58:27598e)
  • [3] K. Appel, W. Haken, and J. Koch, Every planar map is four-colorable, Illinois J. Math. 21 (1977), 429-567. MR 0543792 (58:27598a)
  • [4] M. Behzad, G. Chartrand, and L. Lesniak-Foster, Graphs and Digraphs, Prindle, Weber & Schmidt, Boston, 1979. MR 525578 (80f:05019)
  • [5] D. Gale, The game of Hex and the Brouwer fixed point theorem, Amer. Math. Monthly 86 (1979), 818-827. MR 551501 (81b:90157)
  • [6] R. Lipton and R. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), 177-189. MR 524495 (80k:68050)

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