Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949922 | Discrete Applied Mathematics | 2016 | 9 Pages |
Abstract
A Grünbaum coloring of a triangulation G on a surface is a 3-edge coloring of G such that each face of G receives three distinct colors on its boundary edges. In this paper, we prove that every Fisk triangulation on the projective plane P has a Grünbaum coloring, where a “Fisk triangulation” is one with exactly two odd degree vertices such that the two odd vertices are adjacent. To prove the theorem, we establish a generating theorem for Fisk triangulations on P. Moreover, we show that a triangulation G on P has a Grünbaum coloring with each color-induced subgraph connected if and only if every vertex of G has even degree.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michiko Kasai, Naoki Matsumoto, Atsuhiro Nakamoto,