Publication details
Non-Rainbow Colorings of 3-, 4-and 5-Connected Plane Graphs
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Graph Theory |
| Citation | |
| Doi | http://dx.doi.org/10.1002/jgt.20414 |
| Keywords | plane graphs; non-rainbow colorings |
| Description | 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 |