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

Abstract

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 possible. For maximal graph embedded on the projective plane, we obtain the analogous best bound $\lfloor \frac{2n+1}{3}\rfloor$. The main ingredients in the proofs are classical homological tools. By considering graphs as topological spaces, we introduce the notion of a null coloring, and prove that for any graph $G$ a maximal null coloring $f$ is such that the quotient graph $G/f$ is a forest.