A -color theorem for surfaces of genus

Authors:
Kenneth A. Berman and Jerome L. Paul

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For a set of graphs, define the bounded chromatic number (resp. the bounded path chromatic number ) to be the minimum number of colors for which there exists a constant such that every graph can be vertex -colored so that all but vertices of are properly colored (resp. the length of the longest monochromatic path in is at most ). For the set of toroidal graphs, Albertson and Stromquist [1] conjectured that the bounded chromatic number is 4. For any fixed , let denote the set of graphs of genus . The Albertson-Stromquist conjecture can be extended to the conjecture that for all . In this paper we show that . We also show that the bounded path chromatic number equals 4 for all . Let denote the minimum such that every graph of genus on vertices can be -colored without forcing monochromatic edges (a monochromatic path of length ). We also obtain bounds for and .

**[1]**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**, https://doi.org/10.1090/S0002-9939-1982-0640251-3**[2]**K. Appel and W. Haken,*Every planar map is four colorable. I. Discharging*, Illinois J. Math.**21**(1977), no. 3, 429–490. MR**0543792**

K. Appel, W. Haken, and J. Koch,*Every planar map is four colorable. II. Reducibility*, Illinois J. Math.**21**(1977), no. 3, 491–567. MR**0543793**

K. Appel and W. Haken,*The class check lists corresponding to the supplement: “Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429–490)*, Illinois J. Math.**21**(1977), no. 3, C1-C210. (microfiche supplement). MR**0543794**

K. Appel and W. Haken,*Supplement to: “Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429–490) by Appel and Haken; “II. Reducibility” (ibid. 21 (1977), no. 3, 491–567) by Appel, Haken and J. Koch*, Illinois J. Math.**21**(1977), no. 3, 1–251. (microfiche supplement). MR**0543795**

Kenneth Appel and Wolfgang Haken,*The solution of the four-color-map problem*, Sci. Amer.**237**(1977), no. 4, 108–121, 152. MR**0543796**, https://doi.org/10.1038/scientificamerican1077-108

Kenneth Appel and Wolfgang Haken,*Every planar map is four colorable*, J. Recreational Math.**9**(1976/77), no. 3, 161–169. MR**0543797****[3]**K. Appel and W. Haken,*Every planar map is four colorable. I. Discharging*, Illinois J. Math.**21**(1977), no. 3, 429–490. MR**0543792**

K. Appel, W. Haken, and J. Koch,*Every planar map is four colorable. II. Reducibility*, Illinois J. Math.**21**(1977), no. 3, 491–567. MR**0543793**

K. Appel and W. Haken,*The class check lists corresponding to the supplement: “Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429–490)*, Illinois J. Math.**21**(1977), no. 3, C1-C210. (microfiche supplement). MR**0543794**

K. Appel and W. Haken,*Supplement to: “Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429–490) by Appel and Haken; “II. Reducibility” (ibid. 21 (1977), no. 3, 491–567) by Appel, Haken and J. Koch*, Illinois J. Math.**21**(1977), no. 3, 1–251. (microfiche supplement). MR**0543795**

Kenneth Appel and Wolfgang Haken,*The solution of the four-color-map problem*, Sci. Amer.**237**(1977), no. 4, 108–121, 152. MR**0543796**, https://doi.org/10.1038/scientificamerican1077-108

Kenneth Appel and Wolfgang Haken,*Every planar map is four colorable*, J. Recreational Math.**9**(1976/77), no. 3, 161–169. MR**0543797****[4]**Mehdi Behzad, Gary Chartrand, and Linda Lesniak-Foster,*Graphs & digraphs*, PWS Publishers, Boston, Mass., 1979. MR**525578****[5]**David Gale,*The game of Hex and the Brouwer fixed-point theorem*, Amer. Math. Monthly**86**(1979), no. 10, 818–827. MR**551501**, https://doi.org/10.2307/2320146**[6]**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**, https://doi.org/10.1137/0136016

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

Retrieve articles in all journals with MSC: 05C15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1989-0949874-1

Keywords:
Vertex coloring,
genus ,
chromatic number

Article copyright:
© Copyright 1989
American Mathematical Society