Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There is an exercise in Distributed Algorithm I have some difficulties to solve. There are few ideas, however nothing useful at the time. I will appreciate any help with it.

Graph $G$ is a $k$-tree if it's possible to divide all it's edges to $k$ trees ($k$ subgraphs without a loop). Given network $N$ every processor knows it's parent and it's children in every tree. Using algorithm for 3-coloring of an arbitrary tree (as describe in Vertex Coloring) show that the given graph $G$ is $3k$-colorable in the same time complexity $O(\log^*n)$.

Ideas: every vertex $v$ could belong to one or more trees among $k$ trees. For every particular tree vertex $v$ belongs to, vertex $v$ knows it's parent in this tree and it's children in this tree. Exercise asks to color a graph $G$ in $3k$ colors. Running the mentioned algorithm for any particular tree we will get correct 3-colorable $k$ trees, each vertex will have $m$ different color labels, where $m$ is number of trees, vertex $v$ belongs to.

Now the difficult part, concatenation of all $m$ color labels in one color for vertex $v$ will result in $3^k$ different colors for graph $G$.

In general, simplification of the problem is on the picture.

enter image description here

Vertices $v$ and $u$ are connected by an edge (on the picture the edge belongs to the 1 tree, in principle it doesn't matter, we could draw a parallel edge that belongs to 2 tree), $v$ and $u$ belong to 1 tree and 2 tree. After running 3-colorability algorithm for every tree we will get the correct colorability, now the problem is to make color assignments to vertices $v$ and $u$ as vertices of the graph $G$ based on the color assignment of these vertices for 1 tree and 2 tree, and of course because $u$ and $v$ are connected by an edge in graph $G$, the colors should be different.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.