Conjectures on uniquely 3-edge-colorable graphs
Conjectures on uniquely 3-edge-colorable graphs
复制标题
关于唯一 3 边可着色图的猜想
DOI：
10.11575/cdm.v12i1.62581
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Naoki Matsumoto
中科院分区：
文献类型：
--
作者：
Naoki Matsumoto
一个图G是唯一k边可着色的，如果G的色指数为k，且G的每两个k边着色都将E（G）划分为k个独立的子集.对任意k\ne 3$，唯一k$-边可着色图G$被完全刻画：$G\cong K_2$（若k=1$），$G$是路或偶圈（若k=2$），$G$是星星（若k\geq 4$）。另一方面，存在无穷多个唯一3-边可着色图，因此，有许多刻画唯一3-边可着色图的方法。本文引入了一个新的猜想，它把唯一3-边可着色平面图的图与唯一3-边可着色非平面图的图联系起来。
A graph $G$ is {\it uniquely k-edge-colorable} if the chromatic index of $G$ is $k$ and every two $k$-edge-colorings of $G$ produce the same partition of $E(G)$ into $k$ independent subsets. For any $k\ne 3$, a uniquely $k$-edge-colorable graph $G$ is completely characterized; $G\cong K_2$ if $k=1$, $G$ is a path or an even cycle if $k=2$, and $G$ is a star $K_{1,k}$ if $k\geq 4$. On the other hand, there are infinitely many uniquely 3-edge-colorable graphs, and hence, there are many conjectures for the characterization of uniquely 3-edge-colorable graphs. In this paper, we introduce a new conjecture which connects conjectures of uniquely 3-edge-colorable planar graphs with those of uniquely 3-edge-colorable non-planar graphs.