We are talking about one-round coloring algorithms for distributed graphs.

In "On the complexity of distributed graph coloring" (theorem 5.1) Kuhn and Wattenhoffer presented a one-round algorithm to transform an $m$-coloring to a $q$-coloring, where $q = m(d+1)/(d+2)$ ($d$ is the max degree). We can show that if $m >= d+2$, then $q <= m-1$. [Therefore the algorithm returns a smaller coloring, as long as $m >= d+2$]

They mention that by applying this one-round algorithm over and over, we can transform an $m$-coloring to a $(d+1)$-coloring in $O(d \log(m/d))$ rounds. I don't understand how they reached this number.

I thought that the number of rounds n needed to fulfill the equation:

$m((d+1)/(d+2))^n = d+1$

Because $m$ is the starting coloring, and each round we get a lower coloring by a factor of $(d+1)/(d+2)$. But this doesn't yield the proper result for $n$. Why is it wrong? We want to get $n = O(d\log(m/d))$.

The algorithm itself isn't very complicated and I don't think will contribute to the question; basically for every color that is larger than $q$, we choose for him a color from $\{ 1,\ldots,q \}$ in a way that ensures it is a legal coloring.

Anybody has any insights about the number of rounds needed to achieve a $(d+1)$-coloring?


1 Answer 1


A friend helped me, the equation I wrote was correct. I simply didn't develop the result enough to bring it to the desired form. I will post more details when I have time. Edit: what I needed to achieve the desired result is:

$log(a/b)/log(c/d) = log(b/a)/log(d/c)$

And that we should use Taylor expansion to say $log(1+1/d+1) =~ d+1$ as 1/x+1 -> 0.

If anybody needs help contact me.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.