# Coloring graph with 3 colors

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: 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.

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.
• 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. – Ben Oct 13 '15 at 2:11
• 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? – user1812 Oct 13 '15 at 2:18
• 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. – Ben Oct 13 '15 at 2:22