科研之友
微信
新浪微博
Facebook
分享链接
摘要
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.
- 出版日期2010-2
