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

DOI10.1016/J.DAM.2015.04.007zbMATH Open1339.05106arXiv1210.6831OpenAlexW1513441663MaRDI QIDQ299082FDOQ299082

Authors: Amanda Montejano, Jorge L. Arocha 

Publication date: 22 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: For maximal planar graphs of order $ngeq4$, we prove that a vertex--coloring containing no rainbow faces uses at most $lfloorfrac2n-13floor$ colors, and this is best possible. For maximal graph embedded on the projective plane, we obtain the analogous best bound $lfloorfrac2n+13floor$. 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.

Full work available at URL: https://arxiv.org/abs/1210.6831

Recommendations

• Non-rainbow colorings of 3-, 4- and 5-connected plane graphs
• Matchings and nonrainbow colorings
• Triad colorings of triangulations on closed surfaces
• Facial achromatic number of triangulations on the sphere
• The distinguishing chromatic numbers of triangulations on the projective plane

zbMATH Keywords

anti-Ramsey theorynon-rainbow coloringssphere and projective plane triangulations

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Generalized Ramsey theory (05C55)

Cites Work

• Graphs, surfaces and homology
• Maximum face-constrained coloring of plane graphs
• Tight and untight triangulations of surfaces by complete graphs
• Looseness ranges of triangulations on closed surfaces
• On the minimum size of tight hypergraphs
• Rainbowness of cubic plane graphs
• Colorings of planar graphs with no rainbow faces

Cited In (1)

• On the balanced upper chromatic number of cyclic projective planes and projective spaces

This page was built for publication: Null and non-rainbow colorings of projective plane and sphere triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299082)