2017/09/04 by Jukka Kohonen, Kohonen, Jukka, Janne H. Korhonen +7
Computer Science · #68W15 #Advanced Graph Theory Research #C.2.4 #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1709.00901
openalex publication_date 2017/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a new, simple distributed algorithm for graph colouring in paths and cycles. Our algorithm is fast and self-contained, it does not need any globally consistent orientation, and it reduces the number of colours from 10100 to 3 in three iterations.