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