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