Linear algorithms for edge-coloring trees and unicyclic graphs

DOI10.1016/0020-0190(79)90049-8zbMATH Open0415.68030OpenAlexW1974473207MaRDI QIDQ600259FDOQ600259

Sandra M. Hedetniemi, Stephen T. 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

• Title not available (Why is that?)
• On small graphs critical with respect to edge colourings
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)