Publication details
Colorings of plane graphs with no rainbow faces
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | Combinatorica : an international journal of the János Bolyai Mathematical Society |
| Citation | |
| Doi | http://dx.doi.org/10.1007/s00493-006-0012-3 |
| Description | 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. |