14
$\begingroup$

Let there be two players, $A$ and $B$, and a map.

They now play a game such that:

  • Player $A$ picks a region and player $B$ colors it such that the region is a different color than all adjacent regions.

  • Player $B$ wins if at the end of the game, the map is colored such that no two adjacent regions are the same color. Player $A$ wins if at any point in time that becomes impossible.

If there are five available colors, does player $A$ have a winning strategy for every possible map?

$\endgroup$
10
  • 2
    $\begingroup$ What's the origin of this problem? What are your thoughts on it? How much do you know about graph coloring? $\endgroup$ May 1, 2020 at 18:21
  • $\begingroup$ I know that in a 6-color version player A has a relatively simple winning solution. $\endgroup$ May 1, 2020 at 18:22
  • 1
    $\begingroup$ It seems that the strategy for A is just picking regions with most adjacent colored regions. I might be wrong, though. $\endgroup$ May 1, 2020 at 18:26
  • $\begingroup$ Do you have a link or reference for the $6$-color version? $\endgroup$
    – saulspatz
    May 1, 2020 at 18:29
  • 7
    $\begingroup$ Any planar graph will always have vertices with degree <6. As such these can be coloured no matter the coloring of the surrounding vertices. So you just remove a random vertice with d<6 and keep doing this until there are no vertices left. (when you remove a vertex all surrounding vertexes will have their degree reduced by 1). Then you pick the vertices in the opposite order for the purpose of colouring. At every stage a vertex is picked that has <6 already coloured neighbours. So each vertex will be possible to colour no matter what colours have been use for previous vertexs. $\endgroup$ May 2, 2020 at 9:56

1 Answer 1

3
+50
$\begingroup$

There is a winning strategy for Player A.

If Player A runs the optimal graph coloring algorithm with a specific modification they can win. The algorithm is described briefly here:

Algorithm $\text{Optimal-Color}(G)$

  1. Initially all the vertices of the graph $G:=(V,E)$ are not colored

  2. Initialize $All \leftarrow \{red, green, blue, yellow, black\}$, the set of all colors

  3. $UncoloredDegree(v)$ is the number of neighbors of $v$ that are uncolored and $ColoredDegree(v)$ is the number of neighbors of $v$ that are colored

  4. $Pick(G)$ is a function that picks the uncolored vertex $v$ with the highest $ColoredDegree(v)$. If two vertices have the same colored degree, the one with the higher degree is picked. A tie on degree is broken arbitrarily.

  5. $ConflictColors(v)$ is the set of colors of colored neighboring vertices of $v$

  6. $Color(v)$ is a function that colors the vertex $v$ using a color $c \in All \backslash ConflictColors(v)$

  7. $Remove(v, G)$ is a function that removes the vertex $v$ from $G$ and deletes all incident edges of the vertex $v$ while retaining the neighbors of $v$ in the graph (The degrees of the vertices are updated automatically)

  8. While $\exists v \in G$ having $UncoloredDegree(v) \gt 0$

    a. $v = Pick(G)$

    b. $Color(v)$

    c. $G_v = \text{ the connected subgraph of $G$ }$.

    d. While $G_v$ has an uncolored neighbor vertex

    $n = Pick(G_v)$

    $Color(n)$

    End While

    e. $Remove(v, G)$

  9. End While

End Algorithm

Analysis. This is the standard graph coloring algorithm. After the highest degree vertex and its neighbors are colored, the vertex is removed, leaving its colored neighboring vertices in the graph. All its neighbors degree is now reduced by $1$. By definition the set of colors used for the neighbors of $v$ cannot conflict with the chosen color of $v$. Once $v$ is removed, its color is no longer in conflict, so in Step 5. it becomes available for potential use to color another node in a subsequent step.

Also, it does not matter which color from the non-conflicting colors is chosen in each step. This is the key reason why this is a winning strategy for Player A.

The algorithm terminates because at some point all nodes will be colored and the While Loop in Steps 8-9. stops.

Analysis of the adversarial game In the game outlined in the question, the vertex selection decision is taken by Player A and only the coloring decision is taken by Player B. Vertex selection happens in steps 8.a and 8.d.

Although it looks like Player B has free will and choice, they cannot win because the color selection for a vertex has to be done using non-conflicting colors, if such a selection is possible. With 5 colors, there will always be a non-conflicting color available to choose, regardless of which non-conflicting sequence of colors have been chosen prior.

As long as such non-conflicting selections are made every step of the way, the game terminates with all vertices colored (i.e., Player A wins).

Non-conflicting selections can always be made by coloring triangles with $v$ as one of the vertices (the apex) of the triangle and choosing two non-conflicting colors for the other two vertices. The coloring decisions of two triangles apexed on the same vertex can be done without an additional color use if the two triangles don't share a side. In the example below vertex $8$ is the apex.

Triangles coloring with shared apex and no shared side

It can also be done if the triangles share a side; just use the color of the vertex opposite the shared side. In the example below, the edge $2-8$ is the shared side.

Triangles coloring with shared side

Once all triangles are colored, we will be left with single edges from $v$ to an uncolored neighbor. Any color other than the color of $v$ is non-conflicting for that neighbor.

If there are no triangles with $v$ as an apex, then a single color different from the color of $v$ is optimal. But even if Player A chooses different colors to suboptimize and sabotage the game, the next coloring for vertex $u$ can be done using the color of $v$ since $v$ is not connected to that uncolored vertex $u$.

Existence of valid coloring of node adjacent to partially colored graph. Suppose $G$ has been partially colored after $v$ has been colored and removed. We want to color vertex $u$ adjacent to a colored vertex $w$ ($w \ne v$ because it has been removed from consideration). We can reuse the color assigned to $v$ as it would be non-conflicting as long as $u-v-w$ is not a triangle. We have already shown that triangles always have a valid coloring. Therefore, a non-conflicting selection can always be made for a node adjacent to a partially colored subgraph.

Illustration

The following illustration shows the step by step coloring of a sample graph.

Illustration for sample graph coloring

The subgraph of $G$ containing vertices $1-2-3-4-5-6-7-8$ in which let us say vertex $8$ with degree $6$ is the maximal degree vertex. The connected neighbor subgraph of $v_8$ is $1-2-3-4-5-6-(8)$. Player B picks a color, say $blue$.

After coloring the max degree vertex

Player A then gives picks the neighbor with highest $ColoredDegree(8)$ which is $1$. Once Player B colors $1$, the next neighbor picked will be $2$. This sequence of $Pick(v)$ ensures that triangles are colored first. Suppose Player B wants to sabotage the game and adversarially chooses different colors for each node, say $1 \leftarrow red, 2 \leftarrow green$.

After Player B colors the vertices 1 and 2

Player A then gives the vertices $7-6$.

After Player B tries to max out colors

The next sequence of vertices for coloring is $4-5-3$ or $5-4-3$. Suppose Player A picks $5$. The choice of non-conflicting colors for $5$ are $\{red, green, yellow, black\}$. Any choice would do. There are three uncolored vertices and $4$ non-conflicting color choices. A valid coloring is possible regardless of which colors Player B chooses (as long as they are non-conflicting in every color assignment).

Completed coloring for vertex 8 and neighbors

References:

All 2-D maps are planar graphs. See accepted answer for Proof that every map produces a planar graph - Four Colour Theorem

Five Color Theorem. We can color any planar graph with 5 colors. See: http://www-math.mit.edu/~djk/18.310/18.310F04/planarity_coloring.html

$\endgroup$
22
  • $\begingroup$ It seems that you are assuming that the graph representing the map does not have vertices of degree $>5$, which is not necessarily true. $\endgroup$ Oct 13, 2020 at 19:59
  • 1
    $\begingroup$ @Arjuna196: Yes, good catch. The average degree is strictly less than 6 but you can have nodes with degree $\gt 5$. I have clarified the answer including addition of a proof for existence of 5-colorings for all subgraphs containing a degree-$5$ or greater vertex. $\endgroup$
    – vvg
    Oct 14, 2020 at 3:52
  • $\begingroup$ What about if ALL the vertices have degree >=5 $\endgroup$ Jun 25, 2023 at 16:13
  • 1
    $\begingroup$ A game on the faces of a dodecahedron / vertices of an icosahedron is more complicated than your algorithm suggests. I'm not sure yet who has an unbeatable strategy for that game. $\endgroup$
    – aschepler
    Jul 15, 2023 at 3:11
  • 2
    $\begingroup$ If A has a winning strategy in general, it must depend on the colors B has chosen so far, and not just which vertices are colored and uncolored. If the game is on the icosahedral graph and B knew ahead of time the order A will choose the regions, then B can invent a map where the last region in the sequence is uncolored and surrounded by five different colors, and just fill in A's requests according to that plan. $\endgroup$
    – aschepler
    Jul 17, 2023 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .