A graph is 1-embeddable in a surface it it embeds so that every edge crosses at most one other edge. The 1-chromatic number of the surface is the maximum chromatic number over all graphs 1-embeddable in that surface.

Ringel asks [R]:

Question: Find the 1-chromatic number of a surface.

The problem arises from considering coupled colorings of graphs on surfaces: simultaneous colorings of the vertices and faces of a graph so that incident or adjacent elements receive different colors. Given a graph G in a surface S, a related graph G' exists which is 1-embedded in S and which is colorable if and only if G has a coupled coloring.

Ringel [R] gave Heawood-type upper bounds based on the Euler-Poincare formula. Borodin showed that the 1-chromatic number of the sphere is 6; for the best proof see [B]. Exact values are also known for the torus, Klein's bottle, projective plane, and several other surfaces. For more references see Jensen and Toft [JT]. The conjectured Heawood bounds are known to be exact up to an additive constant of 34. Similarly, Korzhik gives a construction for the 1-chromatic number of other surfaces. Unfortunately, it is unknown if his construction works for an infinite number of surfaces.

References

[B] O. Borodin, A new proof of the 6 color theorem, manuscript (1989).

[JT] T.R. Jensen and B. Toft, Graph Coloring Problems, John Wiley (1995).

[R] G. Ringel, A nine color theorem for the torus and the Klein bottle, in: The Theory and Applications of Graphs (G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Lesniak Foster, D.R. Lick Eds.) Wiley (1981) 507-515.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat, University of Vermont, Burlington VT, 05405 USA.

Send comments to dan.archdeacon@uvm.edu