Edge colouring line graphs of unicyclic graphs (Q1186166)

A characterization of line graphs of unicyclic graphs is established, and it is proved that the line graph \(G\) of a unicyclic graph is in class 1 unless \(G\) is an odd cycle and an optimal edge colouring of the line graph of a unicyclic graph can be computed in time \(O(| E|)\) (note that the chromatic index problem is known to be \(NP\)-complete, even for line graphs). The results are easily extended to line graphs of graphs in which no two cycles have vertices in common.