Editing Graph coloring (section)

=== Parallel and distributed algorithms ===
<!-- [[Distributed graph coloring]] and [[Cole–Vishkin algorithm]] are redirects to this section -->

It is known that a {{mvar|χ}}-chromatic graph can be {{mvar|c}}-colored in the deterministic LOCAL model, in <math>O(n^{1/\alpha})</math>. rounds, with <math>\alpha = \left\lfloor \frac{c - 1}{\chi - 1} \right\rfloor</math>. A matching lower bound of <math>\Omega(n^{1/\alpha})</math> rounds is also known. This lower bound holds even if quantum computers that can exchange quantum information, possibly with a pre-shared entangled state, are allowed. 

In the field of [[distributed algorithm]]s, graph coloring is closely related to the problem of [[symmetry breaking]]. The current state-of-the-art randomized algorithms are faster for sufficiently large maximum degree Δ than deterministic algorithms. The fastest randomized algorithms employ the [[multi-trials technique]] by Schneider and Wattenhofer.{{sfnp|Schneider|Wattenhofer|2010}}

In a [[symmetric graph]], a [[deterministic algorithm|deterministic]] distributed algorithm cannot find a proper vertex coloring. Some auxiliary information is needed in order to break symmetry. A standard assumption is that initially each node has a ''unique identifier'', for example, from the set {{mset|1, 2, ..., ''n''}}. Put otherwise, we assume that we are given an ''n''-coloring. The challenge is to ''reduce'' the number of colors from ''n'' to, e.g., Δ&nbsp;+&nbsp;1. The more colors are employed, e.g. ''O''(Δ) instead of Δ&nbsp;+&nbsp;1, the fewer communication rounds are required.{{sfnp|Schneider|Wattenhofer|2010}}

A straightforward distributed version of the greedy algorithm for (Δ&nbsp;+&nbsp;1)-coloring requires Θ(''n'') communication rounds in the worst case – information may need to be propagated from one side of the network to another side.

The simplest interesting case is an ''n''-[[cycle graph|cycle]]. Richard Cole and [[Uzi Vishkin]]<ref>{{harvtxt|Cole|Vishkin|1986}}, see also {{harvtxt|Cormen|Leiserson|Rivest|1990|loc = Section 30.5}}.</ref> show that there is a distributed algorithm that reduces the number of colors from ''n'' to ''O''(log&nbsp;''n'') in one synchronous communication step. By iterating the same procedure, it is possible to obtain a 3-coloring of an ''n''-cycle in ''O''({{log-star}}&nbsp;''n'') communication steps (assuming that we have unique node identifiers).

The function {{log-star}}, [[iterated logarithm]], is an extremely slowly growing function, "almost constant". Hence the result by Cole and Vishkin raised the question of whether there is a ''constant-time'' distributed algorithm for 3-coloring an ''n''-cycle. {{harvtxt|Linial|1992}} showed that this is not possible: any deterministic distributed algorithm requires Ω({{log-star}}&nbsp;''n'') communication steps to reduce an ''n''-coloring to a 3-coloring in an ''n''-cycle.

The technique by Cole and Vishkin can be applied in arbitrary bounded-degree graphs as well; the running time is poly(Δ) + ''O''({{log-star}}&nbsp;''n'').{{sfnp|Goldberg|Plotkin|Shannon|1988}} The technique was extended to [[unit disk graph]]s by Schneider and Wattenhofer.{{sfnp|Schneider|Wattenhofer|2008}} The fastest deterministic algorithms for (Δ&nbsp;+&nbsp;1)-coloring for small Δ are due to Leonid Barenboim, Michael Elkin and Fabian Kuhn.<ref>{{harvtxt|Barenboim|Elkin|2009}}; {{harvtxt|Kuhn|2009}}.</ref> The algorithm by Barenboim et al. runs in time ''O''(Δ)&nbsp;+&nbsp;{{log-star}}(''n'')/2, which is optimal in terms of ''n'' since the constant factor 1/2 cannot be improved due to Linial's lower bound. {{harvtxt|Panconesi|Srinivasan|1996}} use network decompositions to compute a Δ+1 coloring in time <math> 2
^{O\left(\sqrt{\log n}\right)} </math>.

The problem of edge coloring has also been studied in the distributed model. {{harvtxt|Panconesi|Rizzi|2001}} achieve a (2Δ&nbsp;&minus;&nbsp;1)-coloring in ''O''(Δ&nbsp;+&nbsp;{{log-star}}&nbsp;''n'') time in this model. The lower bound for distributed vertex coloring due to {{harvtxt|Linial|1992}} applies to the distributed edge coloring problem as well.