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?