z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom