Local conflict coloring

DOI10.1109/FOCS.2016.73MaRDI QIDQ6946435zbMATH OpenFDO

Authors Marc Heinrich, Adrian Kosowski, Pierre Fraigniaud

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2016.73

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(12)

• Graph coloring via degeneracy in streaming and other space-conscious models
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Locally-iterative (+1)-coloring in sublinear (in ) rounds
• Adaptive massively parallel coloring in sparse graphs
• Brief announcement: Simpler and more general distributed coloring based on simple list defective coloring algorithms
• Brief announcement: Local advice and local decompression
• Tight lower bounds in the supported LOCAL model
• Single-conflict colorings of degenerate graphs (extended abstract)
• On strongly and robustly critical graphs
• Optimal (degree+1)-coloring in congested clique
• Distributed edge coloring in time polylogarithmic in \({\Delta }\)
• Weak degeneracy of planar graphs

This page was built for publication: Local conflict coloring

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