Ringel's One-Chromatic Number of Surfaces 



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 10 [K].

Vladimir Korzhik (personal communication) reports the following recent results:

Theorem: There is an integer q such that for any non-orientable surface of genus at least q, the 1-chromatic number of the surface and the Heawood-type bound differ by at most 1.

Theorem: The 1-chromatic of a non-orientable surface agrees with the Heawood-type bound for about 7/12’ths of the surfaces.

Korzhik believes he has a long proof that the 1-chromatic number of a nonorientable surface and the Heawood-type bound always differ by at most one, but the argument may be too involved for publication without settling the problem in its entirety. He reports that there are some difficulties ahead for finding a complete solution.

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).

[K] V. Korzhik, A tighter lower bounding interval for the 1-chromatic number of a surface, Disc. Mathematics , 169 (1997) 95-120.

[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

August, 1995, revised March 2004 by Dan Archdeacon.