Edge colouring line graphs of unicyclic graphs

DOI10.1016/0166-218X(92)90206-PMaRDI QIDQ1186166zbMATH OpenFDO

Authors Leizhen Cai, John Ellis

Publication date 28 June 1992

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(92)90206-P

zbMATH Keywords

edge colouringline graphslinear time algorithmunicyclic graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 3857145
• Chromatic index of graphs with no cycle with a unique chord
• Color-line and proper color-line graphs
• On the edge multicoloring of unicyclic graphs
• The Fibonacci numbers in edge coloured unicyclic graphs

Cites work

• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• NP-completeness of edge-colouring some restricted graphs
• Parallel concepts in graph theory
• The NP-completeness column: An ongoing guide
• The NP-completeness column: an ongoing guide
• The NP-Completeness of Edge-Coloring

Cited in

(4)

• Color-line and proper color-line graphs
• scientific article; zbMATH DE number 3857145 (Why is no real title available?)
• Measures of edge-uncolorability
• On the normalized Laplacian spectral radii of a graph and its line graph

This page was built for publication: Edge colouring line graphs of unicyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186166)