Linear algorithms for edge-coloring trees and unicyclic graphs

DOI10.1016/0020-0190(79)90049-8zbMath0415.68030OpenAlexW1974473207MaRDI QIDQ600259

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

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

Related Items

Efficient Vertex- and Edge-Coloring of Outerplanar Graphs, A linear-time algorithm for finding a minimum spanning pseudoforest, The complexity of scheduling independent two-processor tasks on dedicated processors, A linear time algorithm for edge coloring of binomial trees, Optimally edge-colouring outerplanar graphs is in NC, Unnamed Item, A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles

Cites Work

• On small graphs critical with respect to edge colourings
• Using euler partitions to edge color bipartite multigraphs
• Unnamed Item
• Unnamed Item