Abstract

Graph coloring is a fascinating research area in graph theory, with many challenging open
problems, deep results and sophiscated tools. The most well-known result is the Four Color Theorem: In every map,
the countries (connected regions in the plane) can be colored with four colors so that any two neighboring countries
have distinct colors. In this talk, we consider a variation of the coloring problem: a coloring produced through a
game. Take an arbitrary map and a set of colors. Two players, Alice and Bob, alternate their turns in coloring the
countries, subject to the constraint that neighboring countries must be assigned distinct colors. Alice wins the game
if eventually every country is coloured, and Bob win if there is a country uncoloured but all the colors have been
used by its neighboring countries. The problem is how many colors are needed for Alice to have a winning strategy. I
shall explain some tools used in the study of this problem, and survey development in this area.