# zbMATH — the first resource for mathematics

Simple distributed $$\Delta+1$$-coloring of graphs. (English) Zbl 1002.68202
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.

##### 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
Full Text: