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

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]**M. Albertson and W. Stromquist,*Locally planar toroidal graphs are**-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)**

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