3-coloring an unrooted tree in O(log n . log * n) time
We know that in any tree there are at least a constant fraction of vertices are of degree <= 2. Now in the first step let the set of all vertices of degree <= 2 form a new set V1 and be removed from the original set V. Now again V-V1 is a tree (or a forest) – repeat above step until you get sets of vertices V1, V2, V3, … such that the maximum degree of any vertex in any Vi is 2. Clearly the graph formed by the union of these sets (including the edges) is a disconnected graph with degree at most 2 and each of these vertex sets is disjoint. Also note that there will be O(log n) such sets.

Now color this graph formed by the union of the sets Vi using 3 colors and the Cole Vishkin algorithm in O(log n. log *n) time.

Finally, we need to combine these disjoint graphs. For each follow the procedure given below.
For every color check which vertices in that particular subgraph are colored by it.
Now for every such vertex identified in step 1 color it permanently with the color max{{1,2,3} – set of all colors of neighbors of vertex in partially reconstructed graph}
Do not consider such permanently colored vertices in further iterations.
Once all vertices in a given subgraph are permanently colored include that in the partially reconstructed graph and move on to the next subgraph.

Reference: Parallel Symmetry Breaking In Sparse Graphs - Goldberg