Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane
Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane
复制标题
DOI：
10.1007/s00493-021-4330-2
复制
发表时间：
2022-05
期刊：
影响因子：
1.1
通讯作者：
K. Ozeki
中科院分区：
文献类型：
--
作者：
K. Ozeki
一个三次图G在一个双色圈C上的一个3-边染色的Kempe开关交换了C上的颜色，从而产生了G的一个新的3-边染色。如果两个3-边着色图可以通过一系列Kempe开关相互求出，则它们是Kempe等价的。菲斯克证明了三次二部平面图中任意两个3-边染色是Kempe等价的。本文得到了这个定理的一个类似结果，并证明了三次二部射影平面图G的所有3-边染色都是两两Kempe等价的当且仅当G在射影平面中有一个嵌入，使得对偶三角剖分G * 的色数至少为5.作为本文结果的一个副产品，我们证明了对于嵌入在射影平面上的三次图G *，如果对偶图G * 不是4-顶点可染的，则列表边着色猜想成立。
A Kempe switch of a 3-edge-coloring of a cubic graphGon a bicolored cycleCswaps the colors onCand gives rise to a new 3-edge-coloring ofG. Two 3-edge-colorings ofGare Kempe equivalent if they can be obtained from each other by a sequence of Kempe switches. Fisk proved that any two 3-edge-colorings in a cubic bipartite planar graph are Kempe equivalent. In this paper, we obtain an analog of this theorem and prove that all 3-edge-colorings of a cubic bipartite projective-planar graphGare pairwise Kempe equivalent if and only ifGhas an embedding in the projective plane such that the chromatic number of the dual triangulationG* is at least 5. As a by-product of the results in this paper, we prove that the list-edge-coloring conjecture holds for cubic graphsGembedded on the projective plane provided that the dualG* is not 4-vertex-colorable.