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

摘要

By considering graphs as topological spaces we introduce, at the level of homology, the notion of a null coloring, which provides new information on the task of clarifying the structure of cycles in a graph. We prove that for any graph G a maximal null coloring f is such that the quotient graph G/f is acyclic. As an application, for maximal planar graphs (sphere triangulations) of order n >= 4, we prove that a vertex-coloring containing no rainbow faces uses at most [2n-1/3] colors, and this is best possible. For maximal graphs embedded on the projective plane we obtain the analogous best bound [2n+1/3] (C) 2015 Elsevier B.V. All rights reserved.