The Map-Coloring game

Tomasz Bartnicki, Jarosław Grytczuk, Henry Kierstead, Xuding Zhu

Research output: Chapter in Book/Report/Conference proceedingChapter


Introduction Suppose that Alice wants to color a planar map using four colors in a proper way, that is, so that any two adjacent regions get different colors. Despite the fact that she knows for certain that it is eventually possible, she may fail in her first attempts. Indeed, there are usually many proper partial colorings not extendable to proper colorings of the whole map. Thus, if she is unlucky, she may accidentally create such a bad partial coloring. Now suppose that Alice asks Bob to help her in this task. They color the regions of a map alternately, with Alice going first. Bob agrees to cooperate by respecting the rule of a proper coloring. However, for some reason he does not want the job to be completed—his secret aim is to achieve a bad partial coloring. (For instance, he may wish to start the coloring procedure over and over again just to stay longer in Alice's company.) Is it possible for Alice to complete the coloring somehow, in spite of Bob's insidious plan? If not, then how many additional colors are needed to guarantee that the map can be successfully colored, no matter how clever Bob is? This map-coloring game was invented about twenty-five years ago by Steven J. Brams with the hope of finding a game-theoretic proof of the Four Color Theorem, avoiding perhaps the use of computers.

Original languageEnglish (US)
Title of host publicationMartin Gardner in the Twenty-First Century
PublisherMathematical Association of America
Number of pages12
ISBN (Electronic)9781614448013
ISBN (Print)9780883859131
StatePublished - Jan 1 2012

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'The Map-Coloring game'. Together they form a unique fingerprint.

Cite this