Conjectures on uniquely 3-edge-colorable graphs
Author(s) -
Naoki Matsumoto
Publication year - 2016
Publication title -
university of calgary
Language(s) - English
Resource type - Journals
ISSN - 1715-0868
DOI - 10.11575/cdm.v12i1.62581
Subject(s) - combinatorics , mathematics , edge coloring , planar graph , conjecture , graph , 1 planar graph , partition (number theory) , enhanced data rates for gsm evolution , discrete mathematics , chordal graph , line graph , graph power , computer science , telecommunications
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom