Null and non--rainbow colorings of projective plane and sphere triangulations

Jorge L. Arocha, Amanda Montejano

For maximal planar graphs of order $n\ge 4$, we prove that a vertex--coloring containing no rainbow faces uses at most $\lfloor \frac{2n-1}{3}\rfloor$ colors, and this is best poss…