Brooks Coloring in Parallel

DOI10.1137/0403008MaRDI QIDQ3031926zbMATH OpenOpenAlexFDO

Authors Péter Hajnal, Endre Szemerédi

Publication date 1990

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0403008

zbMATH Keywords

Brooks theoremCRCW PRAM modelNCparallel computation

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An NC algorithm for Brooks' theorem
• A fast parallel algorithm to color a graph with Δ colors
• Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
• scientific article; zbMATH DE number 17674
• The local nature of \(\Delta\)-coloring and its algorithmic applications

Cited in

(6)

• Graph coloring on coarse grained multicomputers
• Local nature of Brooks' colouring for degree 3 graphs
• A note on graph coloring extensions and list-colorings
• 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
• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring

This page was built for publication: Brooks Coloring in Parallel

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