4
$\begingroup$

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.

bejeweled

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?

  • 0
    Are you interested in all planer graphs with vertices of degree 4, or just the square grid type graph?2010-10-04
  • 0
    @ttt the latter2010-10-04

1 Answers 1