Non-rainbow colorings of 3-, 4- and 5-connected plane graphs

Abstract

We prove upper bounds on the number of colors in non-rainbow colorings of planar 3-, 4- and 5-connected graphs. Our bounds are best possible for 3- and 4-connected graphs.

Keywords

• non-rainbow coloring
• plane graphs