A $4$-color theorem for surfaces of genus $g$
HTML articles powered by AMS MathViewer
- by Kenneth A. Berman and Jerome L. Paul PDF
- Proc. Amer. Math. Soc. 105 (1989), 513-522 Request permission
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
- Michael O. Albertson and Walter R. Stromquist, Locally planar toroidal graphs are $5$-colorable, Proc. Amer. Math. Soc. 84 (1982), no. 3, 449–457. MR 640251, DOI 10.1090/S0002-9939-1982-0640251-3
- K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
- K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
- Mehdi Behzad, Gary Chartrand, and Linda Lesniak-Foster, Graphs & digraphs, PWS Publishers, Boston, Mass., 1979. MR 525578
- David Gale, The game of Hex and the Brouwer fixed-point theorem, Amer. Math. Monthly 86 (1979), no. 10, 818–827. MR 551501, DOI 10.2307/2320146
- Richard J. Lipton and Robert Endre Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), no. 2, 177–189. MR 524495, DOI 10.1137/0136016
Additional Information
- © Copyright 1989 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 105 (1989), 513-522
- MSC: Primary 05C15
- DOI: https://doi.org/10.1090/S0002-9939-1989-0949874-1
- MathSciNet review: 949874