An NC algorithm for Brooks' theorem

DOI10.1016/0304-3975(89)90121-7MaRDI QIDQ1124351zbMATH OpenOpenAlexFDO

Authors Howard 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)

Recommendations

• NC algorithms for real algebraic numbers
• Brooks' theorem via the Alon-Tarsi theorem
• An algorithmic proof of a generalization of the birkhoff-von neumann theorem
• A Pseudopolynomial Algorithm for Alexandrov’s Theorem
• Brooks' Theorem and Beyond
• A strengthening of Brooks' theorem
• Algorithms for the Quillen-Suslin theorem
• scientific article; zbMATH DE number 125481
• A class of revised Broyden algorithms
• A computational approach to the Borwein-Ditor theorem

Cites work

• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• A fast parallel algorithm to color a graph with Δ colors
• Coloring planar graphs in parallel
• Efficient parallel algorithms for edge coloring problems
• Some simplified NP-complete graph problems

Cited in

(8)

• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Local nature of Brooks' colouring for degree 3 graphs
• A note on graph coloring extensions and list-colorings
• Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
• Graph coloring on coarse grained multicomputers
• Brooks Coloring in Parallel
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems

This page was built for publication: An NC algorithm for Brooks' theorem

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