1
$\begingroup$

The nodes of the graph $[V, E]$ are the lists $\left[ {{s_1},\,{s_2},\,{s_3}} \right]$ where ${s_j} \in \left\{ {1,2} \right\},\,\,j = 1,2,3$. There is an undirected edge between the nodes $\left[ {{s_1},\,{s_2},\,{s_3}} \right]$ and $\left[ {{t_1},\,{t_2},\,{t_3}} \right]$ if and only if $|{s_1} - {t_1}| + |{s_2} - {t_2}| + |{s_3} - {t_3}|\,\, = \,\,1$. Draw this graph and put the nodes in an order so that the greedy coloring algorithm uses $3$ colors.

My attempt:

I got the following graph:

enter image description here

Now i don't know how to put the nodes in an order so that the greedy coloring algorithm will use $3$ colors instead of obvious $2$ colors.

$\endgroup$
1
$\begingroup$

Lets order the vertices $(211), (111), (122),(112),(212), (222), (221), (121)$

Using the colours $1,2,3$, the greedy algorithm assigns the colours $1$ to $(221)$, $2$ to $(111)$, $1$ to $(122)$, $3$ to $(112)$, $2$ to $(212)$, $3$ to $(222)$, $2$ to $(221)$, and $3$ to $(121)$, giving you a $3$-colouring.

$\endgroup$
  • $\begingroup$ I don't understand how do you connect all vertices according to your ordering? Could you specify the mapping? $\endgroup$ – user1812 Oct 13 '15 at 2:08
  • $\begingroup$ The graph is still the one that you drew, I just used the $(xxx)$ notation as labels for the vertices. Then the ordering just describes when I'm going to colour that vertex. So $(211)$ gets coloured first, then $(111)$ etc. Then applying the greedy algorithm gives the three colouring. $\endgroup$ – Ben Oct 13 '15 at 2:11
  • $\begingroup$ Ok, if we start coloring at $\left( {211} \right) \to \left( {111} \right)$ they are adjacent its fine, but how can we jump to $\left( {122} \right)$, which is not adjacent neither to $\left( {211} \right)$ nor to $\left( {111} \right)$? Does greedy coloring implies that we can choose our next coloring node even if it is not adjacent to any node we already colored? $\endgroup$ – user1812 Oct 13 '15 at 2:18
  • $\begingroup$ You can choose the nodes in any order you want. If you always pick a colour adjacent to one we just coloured, the greedy algorithm always results in a $2$-colouring for this graph. $\endgroup$ – Ben Oct 13 '15 at 2:22
1
$\begingroup$

As I understand the greedy coloring algorithm, and as the question implies, there is no fixed order of the vertices. However, you are required to fix the order of the colors before you begin to apply the algorithm - considering the vertices of the graph in sequence and assigning each vertex its first available color (as per the color order you have chosen).

In this context it seems you might have chosen each next vertex from those connected to the current. In such a case you will get two alternating colors for this graph. What happens if you pick a first vertex and color, and then pick a "distant" vertex for the second vertex?

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.