Grunbaum colorings of triangulations on the projective plane
Grunbaum colorings of triangulations on the projective plane
复制标题
投影平面上三角剖分的格伦鲍姆着色
DOI：
10.1016/j.dam.2016.07.012
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Nakamoto
中科院分区：
文献类型：
--
作者：
M. Kasai;N. Matsumoto;A. Nakamoto
曲面上三角剖分图G的Grünbaum染色是G的3-边染色，使得G的每个面在其边界边上接收三种不同的颜色。本文证明了射影平面P上的每个菲斯克三角剖分都有Grünbaum染色，这里的“菲斯克三角剖分”是指恰好有两个奇度顶点且这两个奇度顶点相邻的三角剖分.为了证明这一定理，我们建立了P上菲斯克三角剖分的生成定理，并证明了P上的三角剖分G具有每个色诱导子图连通的Grünbaum染色当且仅当G的每个顶点都是偶数度.
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.