From:           cet1@cus.cam.ac.uk (Chris Thompson)
Newsgroups:     sci.math
Subject:        Colouring planar maps as a 2-person game
Date:           2 Nov 1996 19:29:07 GMT
Organization:   University of Cambridge, England
Keywords:       graph planar colour game

We seem to be having a lot of map-colouring related stuff on sci.math
recently, so here's something else on the same theme. Arising [oh no!
you've guessed!] from Martin Gardner's "Mathematical Games" column
in Scientific American. Relevant issues: Apr 1981, Jun 1981, Oct 1981.
The idea of the game is attributed to Steven Brams.

Given: a planar graph G, all faces initially uncoloured;
       a palette of n colours;
       two players, MIN and MAX.

The players take it it turns to colour a previously uncoloured face
of G, subject only to the constraint that adjacent faces must not 
have the same colour. If either player cannot move while there are
still uncoloured faces, MAX wins. If all faces become coloured, MIN
wins. Usually, MIN plays first.

Question: is there some finite N such that if n >= N, then MIN can
win whatever G is? If so, what is the least such N?

The following example (due to Lloyd Shapley) shows that N >= 6.
Let G be (the skeleton of) a dodecahedron. MAX's strategy is to
always colour the face opposite MIN's last move, and in the same
colour. It's easy to see that this forces 6 different colours to
be used, so MAX wins if n <= 5.

After Gardner's column described this, Robert High discovered a
20-face map that MAX can win if n <= 6, so that N >= 7. There's
a picture of it in the October 1981 issue: I will post it if there
is enough interest.

Has anything more been discovered about this game since then?
Gardner retired from writing the column at about that time [1981 
was the year he was alternating with Hofstadter].

Chris Thompson
Email: cet1@cam.ac.uk