The technique by Cole and Vishkin can be applied in arbitrary bounded-degree graphs as well; the running time is poly(Δ) + "O"( "n"). The technique was extended to unit disk graphs by Schneider et al. The fastest deterministic algorithms for (Δ + 1)-coloring for small Δ are due to Leonid Barenboim, Michael Elkin and Fabian Kuhn. The algorithm by Barenboim et al. runs in time "O"(Δ) + ("n")/2, which is optimal in terms of "n" since the constant factor 1/2 cannot be improved due to Linial's lower bound. use network decompositions to compute a Δ+1 coloring in time formula_82.