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?
