For maximal planar graphs of order $n\geq 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.
Categories: math.CO