Optimal distributed coloring algorithms for planar graphs in the LOCAL model

DOI10.1137/1.9781611975482.49zbMATH Open1431.68130arXiv1804.00137OpenAlexW2796189574MaRDI QIDQ5236232FDOQ5236232

Authors: Shiri Chechik, Doron Mukhtar 

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: In this paper, we consider distributed coloring for planar graphs with a small number of colors. We present an optimal (up to a constant factor) $O(logn)$ time algorithm for 6-coloring planar graphs. Our algorithm is based on a novel technique that in a nutshell detects small structures that can be easily colored given a proper coloring of the rest of the vertices and removes them from the graph until the graph contains a small enough number of edges. We believe this technique might be of independent interest. In addition, we present a lower bound for 4-coloring planar graphs that essentially shows that any algorithm (deterministic or randomized) for $4$-coloring planar graphs requires $Omega(n)$ rounds. We therefore completely resolve the problems of 4-coloring and 6-coloring for planar graphs in the LOCAL model.

Full work available at URL: https://arxiv.org/abs/1804.00137

Recommendations

• Distributed Coloring in Sparse Graphs with Fewer Colors
• Distributed coloring in sparse graphs with fewer colors
• An optimal distributed \((\Delta+1)\)-coloring algorithm?
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds

Mathematics Subject Classification ID

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

Cited In (7)

• Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
• Distributed coloring in sparse graphs with fewer colors
• Distributed algorithms for the Lovász local lemma and graph coloring
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Distributed coloring and the local structure of unit-disk graphs
• Improved distributed \(\Delta\)-coloring
• Local mending

This page was built for publication: Optimal distributed coloring algorithms for planar graphs in the LOCAL model

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