ON D-DIAGONAL COLORINGS

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 int roduced d-diagonal colorings as a generalization of cyclic colorings a nd diagonal colorings. This paper proves a conjecture of Hornak and Je ndrol that plane quadrangulations have d-diagonal colorings with at mo st 1 + 2 . 3(d+1) colors. A similar result is proven for plane triangu lations. Each of these results extends to the projective plane. Also, a lower bound for the d-diagonal chromatic number is given. (C) 1996 J ohn Wiley & Sons, Inc.