The chromatic index of a cubic graph is either 3 or 4. Edge-Kempe switching, which can be used to transform edge-colorings, is here considered for 3-edge-colorings of cubic graphs. Computational results for edge-Kempe switching of cubic graphs up to order 30 and bipartite cubic graphs up to order 36 are tabulated. Families of cubic graphs of orders $4n+2$ and $4n+4$ with $2^n$ edge-Kempe equivalence classes are presented; it is conjectured that there are no cubic graphs with more edge-Kempe equivalence classes. New families of nonplanar bipartite cubic graphs with exactly one edge-Kempe equivalence class are also obtained. Edge-Kempe switching is further connected to cycle switching of Steiner triple systems, for which an improvement of the established classification algorithm is presented.
翻译：立方图的色素索引为 3 或 4 。 用于 变色 边缘 色 的 Edge- Kempe 切换, 这里考虑用于 立方图 的 3- 边缘 色 。 将 30 和 36 之前 的 双边 立方图的 边缘- Kempe 切换 计算结果制成表格 。 提供了 4n+ 2 美元 和 4n+ 4 美元的 立方图 组合, 配有 $ 2 的 边缘 Kempe 等值类 ; 推测 没有 更多 边边- Kempe 等值 类 的 立方图 。 也获得了 精确为 一种 边缘- Kempe 等值类的非平面 双边 立方图 的新组 。 Edge- Kempe 切换为 Steiner 三 系统 的周期切换为,, 并展示了 既定分类算法的改进 。
相关内容
微信扫码咨询专知VIP会员