Puzzle about the Cube: Coloring the Cayley Graph

You say HTM in 8. I can do 7 by doing what you describe. ;-) Below we find the argument that HTM >= 4: {I, U, U2, U3} are all mutually adjacent. So <= 4 remains.

The group H generated by half face turns (also called the square group) can be colored by two colors, since every half face turn changes the parity of the corners in any of both tetras. More generally, we can color each coset pH with two colors. Now provide the colors red and orange in case p is even and the colors green and blue in case p is odd.

Oops, Rokicki already found this on speedsolvers. So let us formulate a new exercise: allowing quarter slice turns in addition to face turns. I already know the answer. I do not know the answer for adding all slice turns, but I can prove that 8 colors suffice.

Hmm, for QTM it should be quite easy to reduce it below this.

Note that we mean the vertex-coloring of the Cayley graph with the minimum number of colors such that no adjacent vertices have the same color.

For QTM I can assuredly think of a 13-coloring, and for HTM I can think of a 19-coloring, but I think we can do better than this.

For the 19-coloring in HTM, what did you have in mind?

If you take the chromatic number to be the minimum number of colors than I think it should be 2 for QTM and 3 for HTM. Correct?

The 19-coloring is to give the color X0 to the identity then give each of its 18 adjacent neighbors the color Xi where 1 <= i <= 18, then do this again and again. If we find out that an adjacent neighbor has already been colored we remove its color from the list and apply the rest of the colors to the rest of the neighbors...

Can you justify 2 for QTM?

You give an algorithm, but it doesn't work, either in this case, or in general.

I apologize. Your algorithm does indeed work for 19 on HTM (indeed, it works for a d+1 coloring on any graph where each node has degree of d or less).

If we take a position in QTM, it has 12 adjacent neighbors, all of them are either up one level or down one level. So if we color the first level red, the next level green, then red, then green... in such a way that all even levels are green and all odd levels are red, then we have a coloring where no two adjacent positions have the same color...

I hope I am understanding the chromatic number definition.

That is correct. You use two colours - one for positions with even parity, and the other for the odd parity positions. Every move changes the parity in QTM, so every move changes the colour and so there are no adjacent nodes in the Cayley graph with the same colour.

In HTM, 19 colours is certainly enough. I don't follow your reasoning though. With 19 colours you can colour the nodes/positions one by one, and for each node you always are able to choose a colour for it that differs from the at most 18 colours of its neighbours.

The HTM Cayley graph can be done with much fewer than 19 colours. You do need at least 4 colours though, because the four positions reached by applying {I, U, U2, U3} are all mutually adjacent.

Jaap
Jaap's Puzzle Page: http://www.jaapsch.net/puzzles/

Nice to see you here!

So, for QTM, we're comfortable that it's two. (The QTM graph is bipartite, and the chromatic number of bipartite graphs is always 2.)

Yep, so for 4..19 it's gotta be 4 or more, and it's also gotta be 19 or less. There are tighter bounds that you can figure out just with pencil and paper, and it's fun to do so.