Grunbaum colorings of even triangulations on surfaces

Kotrbcik, Michal, Matsumoto, Naoki, Mohar, Bojan, Nakamoto, Atsuhiro, Noguchi, Kenta, Ozeki, Kenta and Vodopivec, Andrej (2018) Grunbaum colorings of even triangulations on surfaces. Journal of Graph Theory, 87 4: 475-491. doi:10.1002/jgt.22169


Author Kotrbcik, Michal
Matsumoto, Naoki
Mohar, Bojan
Nakamoto, Atsuhiro
Noguchi, Kenta
Ozeki, Kenta
Vodopivec, Andrej
Title Grunbaum colorings of even triangulations on surfaces
Journal name Journal of Graph Theory   Check publisher's open access policy
ISSN 0364-9024
1097-0118
Publication date 2018-04-01
Year available 2018
Sub-type Article (original research)
DOI 10.1002/jgt.22169
Open Access Status Not yet assessed
Volume 87
Issue 4
Start page 475
End page 491
Total pages 17
Place of publication Hoboken, NJ., United States
Publisher John Wiley & Sons
Language eng
Abstract A Grunbaum coloring of a triangulation G is a map c : E(G){1,2,3} such that for each face f of G, the three edges of the boundary walk of f are colored by three distinct colors. By Four Color Theorem, it is known that every triangulation on the sphere has a Grunbaum coloring. So, in this article, we investigate the question whether each even (i.e.,Eulerian) triangulation on a surface with representativity at least r has a Grunbaum coloring. We prove that, regardless of the representativity, every even triangulation on a surface F has a Grunbaum coloring as long as F is the projective plane, the torus, or the Klein bottle, and we observe that the same holds for any surface with sufficiently large representativity. On the other hand, we construct even triangulations with no Grunbaum coloring and representativity r=1,2, and 3 for all but finitely many surfaces. In dual terms, our results imply that no snark admits an even map on the projective plane, the torus, or the Klein bottle, and that all but finitely many surfaces admit an even map of a snark with representativity at least3.
Keyword Eulerian Triangulations
Polyhedral Embeddings
Orientable Surfaces
Projective Plane
Snarks
Graphs
Families
Genus
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
HERDC Pre-Audit
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sat, 03 Mar 2018, 20:01:43 EST