# Number of rounds of iterative one-round distributed color reduction

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?

$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.