Informace o publikaci
Colorings of plane graphs with no rainbow faces
| Autoři | |
|---|---|
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Combinatorica : an international journal of the János Bolyai Mathematical Society |
| Citace | |
| Doi | http://dx.doi.org/10.1007/s00493-006-0012-3 |
| Popis | 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. |