Informace o publikaci
Cyclic, diagonal and facial colorings
| Autoři | |
|---|---|
| Rok publikování | 2005 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2004.01.016 |
| Popis | 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. |