An NC algorithm for Brooks' theorem

DOI10.1016/0304-3975(89)90121-7zbMath0678.68062OpenAlexW2074645046MaRDI QIDQ1124351

Howard J. Karloff

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90121-7

zbMATH Keywords

graph coloringBrooks' TheoremNC algorithm

Mathematics Subject Classification ID

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

Related Items

The local nature of \(\Delta\)-coloring and its algorithmic applications, Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM, Graph coloring on coarse grained multicomputers

Cites Work

• Some simplified NP-complete graph problems
• Coloring planar graphs in parallel
• Efficient parallel algorithms for edge coloring problems
• A fast parallel algorithm to color a graph with Δ colors
• Unnamed Item
• Unnamed Item