# What is the minimal coloring of a planar graph with swaps?

I play a game known as Bejeweled (I'm sure some of you have heard of it) which has the following properties:

Given a planar graph with every vertex having degree 4, any path of 3 (or more) contiguous colors is considered "complete." Additionally, any two adjacent vertices may be "swapped" to produce said path. If such a swap exists the board is also said to be "complete." You cannot swap if it does not produce a path of 3 or more contiguous colors.

For the moment I'm ignoring the property that this path must be in a straight line.

What I'd like to do is to limit the number of colors I have so that the board will always be complete (having a path, or a single swap produces the path). Now obviously this is trivially true in the 2 color case, but I want the maximal number of colors. Or more precisely,

What is the minimum number of colors that I need to color a planar graph, with every vertex having degree 4, such that there is no contiguous path of 3 identical colors or such a path cannot be produced by a single swapping of two nodes?

-
Are you interested in all planer graphs with vertices of degree 4, or just the square grid type graph? – tttppp Oct 4 '10 at 10:02
@ttt the latter – tzenes Oct 4 '10 at 14:51

The answer is three. As for a proof:

As stated above two colours is not enough. Every square grid colouring must have either alternating colours uniformly across the grid, or somewhere there are two adjacent vertices of the same colour. In the former case then any swap of vertices will create a three-in-a-row. If there are two in a row of the same colour and we assume it is not possible to get to a three in a row configuration, then all the vertices marked X below must not be colour 1.

.X..X.
XX11XX
.X..X.

With only two colours this clearly creates a problem as all the X vertices must be colour 2.

To show that 3 colours suffices consider the colouring below:

123123
231231
312312
123123

The pattern can be extended to cover an infinitely large grid and it's not possible to swap to get three-in-a-row or even to get a coloured path of length three.

-