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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.