Non‐rainbow colorings of 3‐, 4‐ and 5‐connected plane graphs
Zdenĕk Dvořák, Daniel Král͏̌, Riste Škrekovski · Journal of Graph Theory · 2009
Abstract 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 $\lfloor{{7n-8}\over {9}}\rfloor$ . If G is 4 ‐connected, then the number of colors is at most $\lfloor {{5n-6}\over {8}}\rfloor$ , and for n≡3(mod8), it is at most $\lfloor{{5n-6}\over {8}}\rfloor-1$ . Finally, if G is 5 ‐connected, then the number of colors is at most $\lfloor{{25}\over{58}}{\rm n}-{{22} \over {29}}\rfloor$ . 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. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010