<p>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:</p>

<p>$log(a/b)/log(c/d) = log(b/a)/log(d/c)$</p>

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

<p>If anybody needs help contact me.</p>

CC BY-SA 3.0
2015-11-24T11:08:50.050Z
2015-11-28T18:33:24.607Z
2015-11-28T18:33:24.607Z
Assaf
<p>We are talking about one-round coloring algorithms for distributed graphs.</p>

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

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

<p>I thought that the number of rounds n needed to fulfill the equation:</p>

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

<p>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))$.</p>

<p>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.</p>

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

<dc.distributed-comp><graph-colouring>
Number of rounds of iterative one-round distributed color reduction
Assaf
# Number of rounds of iterative one-round distributed color reduction

(Asked by: username_0 on 2015-11-24)

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?

**Tags:** dc.distributed-comp, graph-colouring


---

## 1 answers

### Answer by username_0 on 2015-11-24. Score: 0 | Accepted answer

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.


---

