Publication details
Cyclic, diagonal and facial colorings
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2004.01.016 |
| Description | In an l-facial coloring, any two different vertices that lie on the same face and are at distance at most l on that face receive distinct colors. The concept of facial colorings extends the well-known concept of cyclic colorings. We prove that [18l/5] + 2 colors suffice for an l-facial coloring of a plane graph. For l = 2, 3 and 4, the upper bounds of 8, 12 and 15 colors are shown. We conjecture that each plane graph has an l-facial coloring with at most 3l + 1 colors. Our results on facial colorings are used to decrease to 16 the upper bound on the number of colors needed for I-diagonal colorings of plane quadrangulations. (C) 2004 Elsevier Ltd. All rights reserved. |