Name
Abstract | ||
|---|---|---|
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. (C) 1996 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1996 | 3.0.CO;2-M" target="_self" class="small-link-text"10.1002/(SICI)1097-0118(199606)22:23.0.CO;2-M | Journal of Graph Theory |
Keywords | Field | DocType |
d-diagonal colorings | Diagonal,Discrete mathematics,Topology,Combinatorics,Gallai–Hasse–Roy–Vitaver theorem,Greedy coloring,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 2 | 0364-9024 |
Citations | PageRank | References |
6 | 0.88 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel P. Sanders | 1 | 471 | 45.56 |
| Yue Zhao | 2 | 46 | 9.35 |