2018/03/31 by Shiri Chechik, Chechik, Shiri, Doron Mukhtar +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1804.00137
arxiv created 2018/03/31 · openalex publication_date 2018/03/31 · arxiv updated 2018/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ω(n) rounds. We therefore completely resolve the problems of 4-coloring and 6-coloring for planar graphs in the LOCAL model.