7
$\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 $A$ wins if at the end of the game, the map is colored such that no two adjacent regions are the same color. Player $B$ wins if at any point in time that becomes impossible.

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

$\endgroup$
6
  • 2
    $\begingroup$ What's the origin of this problem? What are your thoughts on it? How much do you know about graph coloring? $\endgroup$ – Steven Stadnicki May 1 '20 at 18:21
  • $\begingroup$ I know that in a 6-color version player A has a relatively simple winning solution. $\endgroup$ – blademan9999 May 1 '20 at 18:22
  • $\begingroup$ It seems that the strategy for A is just picking regions with most adjacent colored regions. I might be wrong, though. $\endgroup$ – Julian Mejia May 1 '20 at 18:26
  • $\begingroup$ Do you have a link or reference for the $6$-color version? $\endgroup$ – saulspatz May 1 '20 at 18:29
  • 4
    $\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$ – blademan9999 May 2 '20 at 9:56
2
+50
$\begingroup$

Player A wins always. A strategy exists due to the 5-color theorem.

Prerequisites:

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

Strategy:

Player A uses the Five Color Theorem to ensure a 5-coloring of the map as follows:

The average degree of a vertex of planar graph $G$ is, $$6 – {12 \over v}$$ where $v$ is the number of vertices. Therefore, the average degree of a vertex in a planar graph is strictly less than $6$.

If the graph contains no degree-$5$ vertex, the $5$-coloring is trivial.

If the graph contains a degree-$5$ or greater vertex, then Player A chooses the subgraph consisting of the degree-$5$ or greater vertex first for coloring.

Player A then proceeds to color all other degree-$5$ or greater vertices in $G$ by asking Player B to color those vertices in descending order of the degree.

A degree-$5$ or greater subgraph of a planar subgraph where all edges incident on a vertex in the subgraph and emanating from other vertices in the subgraph can be colored with 5-colors. Choose a color for the central node (the degree-$5$ or greater node). This color must be distinct from all other previously colored nodes adjacent to the central node. Color all triangles in the subgraph with colors distinct from the central node, if those vertices are not already colored. You need 2 distinct colors for it. You will be left with only degree-1 vertices for which you can choose a color distinct from the central node.

Now, we are left with only $4$-degree vertices and the $5$-coloring of them is trivial. If none of the neighbors are colored, we can color them with the $5$ colors. If some of them are colored, we can choose the colors from the $5$ that we have to ensure no adjacent vertices are colored the same.

$\endgroup$
2
  • $\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$ – Arjuna196 Oct 13 '20 at 19:59
  • $\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 '20 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.