J 2010

Non-Rainbow Colorings of 3-, 4-and 5-Connected Plane Graphs

DVORAK, Z; Daniel KRÁĽ a R SKREKOVSKI

Základní údaje

Originální název

Non-Rainbow Colorings of 3-, 4-and 5-Connected Plane Graphs

Autoři

DVORAK, Z; Daniel KRÁĽ a R SKREKOVSKI

Vydání

Journal of Graph Theory, HOBOKEN, Wiley, 2010, 0364-9024

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.561

DOI

UT WoS

000273584500004

Klíčová slova anglicky

plane graphs; non-rainbow colorings
Změněno: 6. 11. 2020 09:52, Mgr. Darina Boukalová

Anotace

V originále

We study vertex-colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3-connected plane graph with n vertices, then the number of colors in such a coloring does not exceed left perpendicular7n-8/9right perpendicular. If G is 4-connected, then the number of colors is at most left perpendicular5n-6/8right perpendicular, and for n equivalent to 3(mod8), it is at most left perpendicular5n-6/8right perpendicular - 1. Finally, if G is 5-connected, then the number of colors is at most left perpendicular25/58n - 22/29right perpendicular. The bounds for 3-connected and 4-connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129-145, 2010