Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs
Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs
复制标题
DOI：
10.1016/j.disc.2014.02.014
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
Sarah-marie Belcastro;R. Haas
中科院分区：
文献类型：
--
作者：
Sarah-marie Belcastro;R. Haas
一个图的两个n-边染色是边-Kempe等价的，如果一个可以通过一系列边-Kempe开关从另一个得到.本文证明了当使用3= χ′（G）色时，每一个平面二部三次图都有一个边Kempe等价类.相比之下，我们还展示了无限家庭的非平面二部立方（因此3边着色）图的数量范围内的边肯普等价类时，使用3种颜色。这些结果回答了Mohar提出的一个问题。
Two n-edge colorings of a graph are edge-Kempe equivalent if one can be obtained from the other by a series of edge-Kempe switches. In this work we show every planar bipartite cubic graph has exactly one edge-Kempe equivalence class, when 3= χ′(G) colors are used. In contrast, we also exhibit infinite families of nonplanar bipartite cubic (and thus 3-edge colorable) graphs with a range of numbers of edge-Kempe equivalence classes when using 3 colors. These results address a question raised by Mohar.