Premium
On d ‐diagonal colorings
Author(s) -
Sanders Daniel P.,
Zhao Yue
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199606)22:2<155::aid-jgt6>3.0.co;2-m
Subject(s) - combinatorics , diagonal , mathematics , conjecture , plane (geometry) , generalization , graph , fractional coloring , chromatic scale , projective plane , edge coloring , discrete mathematics , graph power , geometry , mathematical analysis , line graph , correlation
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 · 3 d +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.