Linear algorithms for edge-coloring trees and unicyclic graphs

DOI10.1016/0020-0190(79)90049-8MaRDI QIDQ600259zbMATH OpenOpenAlexFDO

Authors Stephen T. Hedetniemi, Sandra M. Hedetniemi

Publication date 1979

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(79)90049-8

zbMATH Keywords

treecomputational complexityedge-coloringunicyclic graph

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3394154 (Why is no real title available?)
• On small graphs critical with respect to edge colourings
• Using euler partitions to edge color bipartite multigraphs

Cited in

(7)

• A linear-time algorithm for finding a minimum spanning pseudoforest
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• A linear time algorithm for edge coloring of binomial trees
• The complexity of scheduling independent two-processor tasks on dedicated processors
• Optimally edge-colouring outerplanar graphs is in NC
• scientific article; zbMATH DE number 223376 (Why is no real title available?)
• A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles

This page was built for publication: Linear algorithms for edge-coloring trees and unicyclic graphs

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