Informace o publikaci

Cyclic, diagonal and facial colorings

Autoři

KRÁĽ Daniel MADARAS T SKREKOVSKI R

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.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info