Null and non--rainbow colorings of projective plane and sphere triangulations
classification
🧮 math.CO
keywords
graphmaximalnullbestcoloringfracgraphslfloor
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.