Finite fields and the 1‐chromatic number of orientable surfaces
Vladimir P. Korzhik · Journal of Graph Theory · 2009
Abstract The 1‐chromatic number χ1(Sp) of the orientable surface Sp of genus p is the maximum chromatic number of all graphs which can be drawn on the surface so that each edge is crossed by no more than one other edge. We show that if there exists a finite field of order 4m+1, m≥3, then 8m+2≤χ1(S )≤8m+3, where 8m+3 is Ringel's upper bound on χ1(S ). © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 179–184, 2010