Name
Abstract | ||
|---|---|---|
A cyclic coloring is a vertex coloring such that vertices in a face receive different colors. Let Delta be the maximum face degree of a graph. This article shows that plane graphs have cyclic 9/5 Delta-colorings, improving results of Ore and Plummer, and of Borodin. The result is mainly a corollary of a best-possible upper bound on the minimum cyclic degree of a vertex of a plane graph in terms of its maximum face degree. The proof also yields results on the projective plane, as well as for d-diagonal colorings. Also, it is shown that plane graphs with Delta = 5 have cyclic 8-colorings. This result and also the 9/5 Delta result are not necessarily best possible. (C) 1999 Elsevier Science B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0012-365X(99)00018-7 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
cyclic coloring, plane graphs, degree of vertices | Journal | 203 |
Issue | ISSN | Citations |
1-3 | 0012-365X | 22 |
PageRank | References | Authors |
2.32 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oleg V. Borodin | 1 | 639 | 67.41 |
| Daniel P. Sanders | 2 | 471 | 45.56 |
| Yue Zhao | 3 | 22 | 2.32 |