Matchings and Nonrainbow Colorings
Zdenĕk Dvořák, Stanislav Jendrol′, Daniel Král͏̌, Gyula Pap · SIAM Journal on Discrete Mathematics · 2009
We show that the maximum number of colors that can be used in a vertex coloring of a cubic 3-connected plane graph G that avoids a face with vertices of mutually distinct colors (a rainbow face) is equal to $\frac{n}{2}+\mu^*-2$, where n is the number of vertices of G and $\mu^*$ is the size of the maximum matching of the dual graph $G^*$.