pith. sign in

arxiv: 1210.6831 · v1 · pith:O6UNPP2Hnew · submitted 2012-10-25 · 🧮 math.CO

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

classification 🧮 math.CO
keywords graphmaximalnullbestcoloringfracgraphslfloor
0
0 comments X
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.