Conjectures on uniquely 3-edge-colorable graphs

Contributions to Discrete Mathematics

Naoki Matsumoto

关键词: Uniquely coloring;    Edge coloring;    Cubic;   

学科分类：社会科学、人文和艺术（综合）

来源: University of Calgary * Department of Mathematics and Statistics

【 摘 要 】

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 conjecturewhich connects conjectures of uniquely 3-edge-colorable planar graphs with those of uniquely 3-edge-colorable non-planar graphs.

【 授权许可】

Unknown