Graph Coloring Games

There are a number of interesting ways to make a two-player game out of coloring the vertices of graphs. We'll look at a couple.

Setup

For this activity you'll want some printouts of graphs to use as game boards. I've included some here. While you can color with markers or crayons, for replayability I recommend using tokens of some kind. I've used plastic bingo chips because they're cheap and colorful. Here are some options:

JUNWRROW transparent bingo chips (1000 chips in 6 colors for $10)
Royal Bingo transparent bingo chips (1000 chips in 7 colors for $12)
Hebayy transparent bingo chips (600 chips in 8 colors for $8.50)
Coopay opaque bingo chips (900 chips in 6 colors for $15)

For color-blind participants, tokens should be distinguishable in some way other than color. I've never used these fruit counters before, but they're one of the few counters I've seen where each object type is assigned a unique color, which is a helpful property for activities where we still want color to be a visual signifier. Here are some other counters that are advertised as having this property, but I haven't ordered them before and have seen similar sets that will mix and match colors to object types, so be careful!

JOCHA dinosaur counters (48 in 6 colors for $9)
JOCHA animal counters (36 in 6 colors for $11)
PYROSOME ocean animal counters (56 in 8 colors for $9)
PYROSOME transportation counters (36 in 6 colors for $10)

Challenges

In each of the following games, a turn consists of coloring an uncolored vertex (or node) of the graph so that no adjacent (neighboring) vertices have the same color. Each player must color a vertex on their turn, if possible. The game ends when either all of the vertices are colored or no further vertices can be colored without resulting in same-color neighbors. It is important that the number of colors players can choose from is limited, so we'll prescribe some palettes, but students should be encouraged to explore. To keep things fair, students can alternate who plays first or second as they work out strategies and decide whether the first or second player has the advantage.

A. Last Player To Move Wins

In this variant of the game, the last person to be able to make a move wins. This can be interesting with as few as $1-2$ colors. Here are some explorations:

Play a few games on the first path graph (path on $7$ vertices) using only one color.
What's a good strategy for winning? Is it better to play first or second?
Play on some other paths using only one color. Can you find any patterns to your strategy?
How do things change if you have two colors? Three colors?
Play a few games on the first cycle graph (cycle on $8$ vertices) using only one color.
What's a good strategy for winning? Is it better to play first or second?
Play on some other cycles using only one color. Can you find any patterns to your strategy?
How do things change if you have two colors? Three colors?
Play on some of the other graphs, trying to decide who has the advantage and what a good strategy might look like.
Are there ways to tell by looking at a graph and the number of colors whether you would want to be the first or second player? (Your answer doesn't have to apply to all graphs!)

B. First Player Fills, Second Player Blocks

The first player wins if every vertex is colored at the end of the game. The second player wins if there are uncolored vertices but no further moves are possible. The sweet spot for this tends to be around $3-5$ colors. Here are some explorations:

Play a few games on the first path graph using two colors. Who wins? Is this an interesting game?
Now try playing with three colors. Who wins? Is this an interesting game?
Play a few games on the first caterpillar graph using three colors. (This should be more challenging!)
What's a good strategy for winning? Is it better to play first or second?
Now try playing on the second caterpillar graph with three colors. How does the strategy change?
What's different about playing on these caterpillar graphs if you are allowed to use four colors?
What about with five colors?
Play a few games on the graph that looks like the outline of a cube using three colors. Who has the advantage and what's their strategy?
Play on some of the other graphs, trying to decide who has the advantage and what a good strategy might look like.
Are there ways to tell by looking at a graph and the number of colors whether you would want to be the first or second player? (Your answer doesn't have to apply to all graphs!)

Notes

For more technical parts of the discussion below, a couple ideas from graph theory will be useful.

The degree of a vertex $v$ is the number of edges adjacent to it, and we denote this $\deg v$. The maximum degree a vertex has in a graph $G$ is called the maximum degree of $G$ and denoted $\Delta(G)$. If we have $\Delta(G)+1$ or more colors, then there will be no vertex that cannot be colored before the game is over, since there will always be some color not used on a neighboring vertex.

For a graph $G$, its chromatic number $\chi(G)$ is the least number of colors one can use in a proper vertex coloring (i.e., no adjacent vertices have the same color). Whenever playing with fewer than $\chi(G)$ colors, by definition, some vertices will necessarily be left uncolored at the end of the game.

A. Last Player To Move Wins

Due to the symmetry of player roles and the traditional win condition, this variant is the standard sort of game that can be analyzed using nimbers.
On paths with an odd number of vertices, the first player has a winning strategy with one or two colors. Their first move is to color the middle vertex, dividing the path into two halves. Then, whatever the second player does, the first player can mirror the move on the other half.
On paths with an even number of vertices, the second player has a winning strategy with two colors. Whatever move the first player does, the second player can mirror it across the midpoint of the path using the opposite color.
On paths with an even number of vertices, either player can have the advantage when playing with one color. There is no obvious pattern (it's not even in the OEIS!), but here are the lengths of paths for which the second player has the advantage, which I computed from nimbers using the Sprague-Grundy theorem:
\[ 4, 8, 14, 20, 24, 28, 34, 38, 42, 54, 58, 62, 72, 76, 88, 92, 96, 106, 110, 122, 126, 130, 140, 144, 156, 160, ... \]
On cycles with an even number of vertices, the second player has a winning strategy with one or two colors. Whatever moves the first player makes, the second player can color the diametrically opposite vertex with the same color.
On cycles with an odd number of vertices, the second player has a winning strategy with two colors. After the first player colors a vertex, the second player should skip a vertex and color the next one with the opposite color, so that an uncolored vertex is trapped between two different colors. Drawing a line that cuts the cycle in half through this uncolored vertex, the second player then mirrors the actions of the first player across the line in the opposite color.
On cycles with an odd number of vertices with one color, after the first player plays, the game has been reduced from a cycle on $v$ vertices to a path with $v-3$, since nobody can play in the two spots adjacent to the colored vertex. Since this is the even path case, we know the advantage depends on the number of vertices. Adding $3$ to our sequence above, the first player has the advantage when the number of vertices is:
\[ 3, 7, 11, 17, 23, 27, 31, 37, 41, 45, 57, 61, 65, 75, 79, 91, 95, 99, 109, 113, 125, 129, 133, 143, 147, 159, 163, ... \]
This sequence is in the OEIS, but described in terms of an edge deletion game: Starting with a graph, players delete edges until a vertex is isolated. The player to first isolate a vertex loses. (You might be able to tell how this game relates to ours!)
With both the paths and cycles, since $\Delta(G) \leq 2$, all vertices must be colored by the end of the game when playing with $3$ or more colors. This means that if the number of vertices is odd, the first player wins, while if the number of vertices is even, the second player wins.

B. First Player Fills, Second Player Blocks

This variant was introduced in 1981 by Steven Brams via Martin Gardner in his Scientific American column Mathematical Games. If you want to track down that article these days, it's most easily found in the compendium The Last Recreations, pages 253-254. The game was rediscovered and considered by Hans Bodlaender in a 1991 article.
The role of the second player is to try to set "traps" for the first player, resulting in vertices that cannot be filled in. In this light, a practical way to view the first player's strategy is preventing the second player from successfully setting such traps.

If there is only one color, then any colored vertex sets the trap for neighboring vertices. While it's slightly more complicated with two colors, typically the second player will have little trouble trapping an uncolored vertex between one of each color.
Since a trap at a vertex $v$ requires all colors to have been used on $v$'s neighbors, if the number of colors is $\Delta(G)+1$ or larger, there will always be a color for $v$ that has not been used on its neighbors. This means if the number of colors is $\Delta(G)+1$ or larger, the first player has a winning strategy in the form of "play any color that works."
For this game, researchers have defined the game chromatic number of a graph $G$ to be the least number of colors that the first player needs to win. We'll follow Faigle et al. and denote it $\gamma(G)$. By our discussion,
\[ \chi(G) \leq \gamma(G) \leq \Delta(G)+1 \]
One would expect that the first player has a winning strategy for any number of colors greater than $\gamma(G)$ -- i.e., this game chromatic number is a sort of threshold where the advantage swaps from the second player to the first player. Oddly enough, however, nobody has yet managed to prove that if the first player has a winning strategy on $G$ with $k$ colors, they also have a winning strategy with $k+1$ colors!
The caterpillar graph below was given by Bodlaender as an example of a tree with $\gamma(G) = 4$.

Faigle et al. proved $\gamma(G) \leq 4$ by giving a winning strategy: Player 1 starts by coloring any vertex $r$ (which we'll think of as the root of the tree) and starts a set of vertices, $T = \{r\}$. Whenever Player 2 colors a vertex $v$, Player 1 looks at the path $P$ from $r$ to $v$ and finds the vertex $u$ on this path closest to $v$ that is already in their set $T$. Player 1 then adds every vertex in $P$ to $T$ and does the following:
- If $u$ is uncolored, Player $1$ colors it any allowable color.
- If $u$ is colored, Player $1$ checks if there is an uncolored vertex in $T$.
The graph given by the skeletal frame of the icosahedron pictured below was given by Lloyd Shapley as a planar graph with $\gamma(G) = 5$.

Extra Challenges

Here are a couple variants that are easy to jump into with the materials used above:
- Last Person To Move Loses: The misère form of the Last Person to Move Wins variant. Misère variants generally tend to be a bit tougher to analyze.
- First Player Blocks, Second Player Fills: This variant reverses the roles of the First Player Fills, Second Player Blocks variant. The main question is whether the blocker being the first to have to play introduces any new advantages or disadvantages.
Instead of coloring the vertices of a graph, we could instead color the edges. In a proper coloring, no two edges that meet at the same vertex may have the same color. Any of our win conditions can be used in an edge-coloring game.

This post was sponsored by the Julia Robinson Mathematics Festival

Search This Blog

math them