Informace o publikaci
Non-Rainbow Colorings of 3-, 4-and 5-Connected Plane Graphs
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Graph Theory |
| Citace | |
| Doi | http://dx.doi.org/10.1002/jgt.20414 |
| Klíčová slova | plane graphs; non-rainbow colorings |
| Popis | 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 |