J 2006

Colorings of plane graphs with no rainbow faces

JUNGIC, V; Daniel KRÁĽ a R SKREKOVSKI

Základní údaje

Originální název

Colorings of plane graphs with no rainbow faces

Autoři

JUNGIC, V; Daniel KRÁĽ a R SKREKOVSKI

Vydání

Combinatorica : an international journal of the János Bolyai Mathematical Society, Budapest, Mathematical Institute of the Hungarian Academy of Sciences, 2006, 0209-9683

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.784

Označené pro přenos do RIV

Ne

DOI

UT WoS

Změněno: 6. 11. 2020 10:54, Mgr. Darina Boukalová

Anotace

V originále

We prove that each n-vertex plane graph with girth g >= 4 admits a vertex coloring with at least [n/2] +1 colors with no rainbow face, i.e., a face in which all vertices receive distinct colors. This proves a conjecture of Ramamurthi and West. Moreover, we prove for plane graph with girth g >= 5 that there is a vertex coloring with at least [(g-3/g-2)n - (g-7/2(g-2))] if g is odd and [ (g-3/g-2)n - (g-6/2(g-2))] if g is even. The bounds are tight for all pairs of n and g with g >= 4 and n >= 5g/2-3.