Simple and near-optimal distributed coloring for sparse graphs

DOI10.4230/LIPICS.DISC.2017.20MaRDI QIDQ6487492zbMATH OpenFDO

Authors Mohsen Ghaffari, Christiana Lymouri

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2017.20

zbMATH Keywords

arboricitydistributed graph algorithmsgraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed graph coloring in a few rounds
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed Coloring in Sparse Graphs with Fewer Colors
• Distributed coloring in sparse graphs with fewer colors

Cited in

(16)

• Simple distributed +1-coloring of graphs
• Distributed coloring in sparse graphs with fewer colors
• Property testing of planarity in the \textsf{CONGEST} model
• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• Distributed graph coloring in a few rounds
• Simple Distributed Δ + 1 Coloring in the SINR Model
• Distributed degree splitting, edge coloring, and orientations
• Distributed arboricity-dependent graph coloring via all-to-all communication
• Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
• Distributed Coloring in Sparse Graphs with Fewer Colors
• scientific article; zbMATH DE number 956854 (Why is no real title available?)
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Improved dynamic colouring of sparse graphs
• Graph coloring via degeneracy in streaming and other space-conscious models
• Adaptive massively parallel coloring in sparse graphs
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism

This page was built for publication: Simple and near-optimal distributed coloring for sparse graphs

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