**The d-Diagonal Chromatic
Number**

This problem is due to M. Hornak and S. Jendrol'.

Two vertices *x,y* of an embedded graph *G*
are *d-diagonally adjacent* if there is a set *S* of at most
*d* edges such that *x* and *y* are incident with a common
face of *G-S*. Let a *d-diagonal coloring* be a vertex coloring
such that each pair of *d*-diagonally adjacent vertices get different
colors. Any bound on the *d*-diagonal chromatic number of a class of
graphs must clearly depend on the maximum face size *Delta* of these
graphs.

The 0-diagonal chromatic number was originally known as
the cyclic chromatic number. Here any two vertices on the same face
receive distinct colors. For plane graphs, as shown by Borodin, Sanders,
and Zhao, this number is between [3 *Delta* / 2] and [9 *Delta*
/ 5] where [*x*] refers to the integer part of *x*. The upper
bound was
improved to [5 *Delta* / 3] by Sanders and Zhou. For *Delta
= 3*, the 1-diagonal number of plane graphs is conjectured to be 9 by
Bouchet, Fouquet, Jolivet, and Riviere, but the best known upper bound is
10 by Sanders and Zhao. For *Delta = 3*, Borodin gave an upper bound
of *(13+(169-48chi)^{1/2})/2* for the 1-diagonal chromatic number of
a general surface of Euler characteristic *chi*.

For plane
graphs, the *d*-diagonal chromatic number is known to be between
*Delta(Delta-1)^{d/2}* and *(5/2)Delta(Delta-1)^d*, with
different improvements for each *Delta*, as shown by Sanders and
Zhao.

**Problem:** *For each surface, find the*
d*-diagonal chromatic number in terms of the maximum face size.*

Many subproblems are also interesting. The only best possible results known are:

*d = 0, Delta = 3,*for every surface (Appel and Haken, Heawood, Franklin, et al.),*d = 0, Delta = 4,*for the plane (Borodin),*d = 0, Delta = 5,*for the projective plane (Borodin, Sanders, and Zhao),*d = 1, Delta = 3,*for the torus (Bouchet, Fouquet, Jolivet, and Riviere).

Submitted by: Daniel Sanders, sanders@graphtheory.com

Send comments to *dan.archdeacon@uvm.edu*

August, 1995. Modified February 8, 2000