Skip to main content
added 5 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

If there is only one edge colouring with $k$ colours of a graph with chromatic index $k$, the graph is calledsaid to be "uniquely edge colouring"colourable". If you search on that phrase (with and without the second "u") you will find that the problem is trivial for $k\le 2$, solved for $k\ge 4$ (only case $K_{1,k}$) and for $k=3$ can be reduced to the case of cubic graphs. For example, see this paper of Andrew Thomason. It is said that an example is the generalized Petersen graph $P(9,2)$.

If there is only one edge colouring with $k$ colours of a graph with chromatic index $k$, the graph is called "uniquely edge colouring". If you search on that phrase (with and without the second "u") you will find that the problem is trivial for $k\le 2$, solved for $k\ge 4$ (only case $K_{1,k}$) and for $k=3$ can be reduced to the case of cubic graphs. For example, see this paper of Andrew Thomason. It is said that an example is the generalized Petersen graph $P(9,2)$.

If there is only one edge colouring with $k$ colours of a graph with chromatic index $k$, the graph is said to be "uniquely edge colourable". If you search on that phrase (with and without the second "u") you will find that the problem is trivial for $k\le 2$, solved for $k\ge 4$ (only case $K_{1,k}$) and for $k=3$ can be reduced to the case of cubic graphs. For example, see this paper of Andrew Thomason. It is said that an example is the generalized Petersen graph $P(9,2)$.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

If there is only one edge colouring with $k$ colours of a graph with chromatic index $k$, the graph is called "uniquely edge colouring". If you search on that phrase (with and without the second "u") you will find that the problem is trivial for $k\le 2$, solved for $k\ge 4$ (only case $K_{1,k}$) and for $k=3$ can be reduced to the case of cubic graphs. For example, see this paper of Andrew Thomason. It is said that an example is the generalized Petersen graph $P(9,2)$.