Faculty of Environment and Information Sciences, Yokohama National University
抄録
A Kempe switch of a 3-edge-coloring of a cubic graph G on a bicolored cycle C swaps the colors on C and gives rise to a new 3-edge-coloring of G. Two 3-edge-colorings of G are 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 graph G are pairwise Kempe equivalent if and only if G has an embedding in the projective plane such that the chromatic number of the dual triangulation G* 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 graphs G embedded on the projective plane provided that the dual G* is not 4-vertex-colorable.
雑誌名
Combinatorica
巻
42
ページ
1451 - 1480
発行年
2022-05-19
ISSN
1439-6912
書誌レコードID
AA10439913
DOI
info:doi/10.1007/s00493-021-4330-2
権利
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s00493-021-4330-2
Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane
kempe_equiv_2021_0930.pdf
(234.2KB)
トップページ