I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time.
The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon.
In short, the idea is ...
Starting from the valid coloring given by the processor ID's, the procedure iteratively reduces the number of bits in the color descriptions by recoloring each nonroot node $v$ with the color obtained by concatenating the index of a bit in which $C_v$ differs from $C_{parent}(v)$ and the value of this bit. The root $r$ concatenates $0$ and $C_r[0]$ to form its new color.
The algorithm terminates after $O(\log^*n)$ iterations.
I don' have the intuitive understanding why it's actually terminates in $O(\log^*n)$ iterations. As it's mentioned in the paper on the final iteration there is the smallest index where two bit string differs is at most 3. So 0th bit and 1th bit could be the same and $2^2=4$, so this two bit will give us 4 colors + another 2 colors for different 3th bit, and in total 8 colors and not 6 like in the paper, and why we cannot proceed further with 2 bits, it's still possible to find different bits and separate them.
I would appreciate a little bit deeper analysis of the algorithm than in the paper.
