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