Johansson, Öjvind Simple distributed \(\Delta+1\)-coloring of graphs. (English) Zbl 1002.68202 Inf. Process. Lett. 70, No. 5, 229-232 (1999). Summary: A very natural randomized algorithm for distributed vertex coloring of graphs is analyzed. Under the assumption that the random choices of processors are mutually independent, the execution time will be \(O(\log n)\) rounds almost always. A small modification of the algorithm is also proposed. Cited in 15 Documents MSC: 68W20 Randomized algorithms 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science 05C15 Coloring of graphs and hypergraphs Keywords:distributed vertex coloring of graphs PDF BibTeX XML Cite \textit{Ö. Johansson}, Inf. Process. Lett. 70, No. 5, 229--232 (1999; Zbl 1002.68202) Full Text: DOI