Conjectures on uniquely 3-edge-colorable graphs


  • Naoki Matsumoto Seikei University



Uniquely coloring, Edge coloring, Cubic


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.


\bibitem{bel} S.-M. Belcastro and R. Haas,
Triangle-free uniquely 3-edge colorable cubic graphs,

\bibitem{Ent} R.C. Entringer,
Spanning cycles of nearly cubic graphs,
{\it J. Combin. Theory B} {\bf 29} (1980), 303--309.

\bibitem{Fi} S. Fiorini,
On the chromatic index of a graph. III. Uniquely edge-colourable graphs.
{\it Quart. J. Math. Oxford Ser.} {\bf 26} (1975), 129--140.

\bibitem{FW} S. Fiorini and R. J. Wilson, Edge colourings of graphs, Selected Topics in Graph Theory,
{\it Academic Press, New York} (1978), 103--126.

\bibitem{fowler} T. Fowler, Unique Coloring of Planar Graphs,
Ph.D. thesis, Georgia Institute of Technology Mathematics Department (1998).

\bibitem{GZ} J.L. Goldwasser and C.-Q. Zhang,
Uniquely Edge-3-Colorable Graphs and Snarks,
{\it Graphs and Combinatorics} {\bf 16} (2000), 257--267.

\bibitem{GK} D. Greenwell and H. V. Kronk, Uniquely line-colorable graphs,
{\it Canad. Math. Bull} {\bf 16} (1973), 525--529.

\bibitem{isa} R. Isaacs,
Infinite families of non-trivial trivalent graphs which are not Tait colorable,
{\it Am. Math. Mon.} {\bf 82} (1975), 221--239.

\bibitem{sey} P.D. Seymour, Sums of circuits,
In Graph Theory and Related Topics (Ed. J.A. Bondy and U.R.S. Murty).
New York: Academic Press (1979), 341--355.

\bibitem{tait} P.G. Tait,
Remarks on the coloring of maps,
{\it Proceeding of the Royal Society of Edinbrugh} {\bf 10} (1880), 501--503, 729.

\bibitem{U4} A. Thomason, Hamiltonian cycles and uniquely edge colourable graphs,
{\it Annals Disc. Math.} {\bf 3} (1978), 259--268.

\bibitem{Zh} C.-Q. Zhang, Hamiltonian weights and unique edge-3-colorings of cubic graphs,
{\it J. Graph Theory} {\bf 20} (1995), 91--99.