Ond-diagonal colorings
Daniel P. Sanders, Yue Zhao · Journal of Graph Theory · 1996
A coloring of a graph embedded on a surface is d-diagonal if any pair of vertices that are in the same face after the deletion of at most d edges of the graph must be colored differently. Hornak and Jendrol introduced d-diagonal colorings as a generalization of cyclic colorings and diagonal colorings. This paper proves a conjecture of Hornak and Jendrol that plane quadrangulations have d-diagonal colorings with at most 1 + 2 · 3d+1 colors. A similar result is proven for plane triangulations. Each of these results extends to the projective plane. Also, a lower bound for the d-diagonal chromatic number is given. © 1996 John Wiley & Sons, Inc.