| Article ID: | iaor19921848 |
| Country: | Netherlands |
| Volume: | 36 |
| Issue: | 1 |
| Start Page Number: | 75 |
| End Page Number: | 82 |
| Publication Date: | Mar 1992 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Cai Leizhen, Ellis John A. |
The chromatic index problem is known to be NP-complete, even for line graphs. In this paper the authors show that the chromatic index of the line graph of a unicyclic graph is equal to its maximum degree unless it is an odd cycle. The construction used in the proof implies a linear time algorithm for computing an optimal edge colouring of such a line graph. The results are easily extended to line graphs of graphs in which no two cycles have vertices in common.