Undergraduate Math Club, Professor Karen Collins (Wes): 'The Map-Coloring Game'

Thursday, November 13, 2014
12:00 PM - 1:00 PM (ET)
ESC 109
Event Type
Academic Calendar
David Constantine, x2167
Math/CS Other

Mathematical conjectures which are easy to state but hard to prove can be the most exciting. For example, the Four-Color Theorem (4CT), which states that the regions of any map may be colored with 4 colors so that adjacent regions are colored distinctly, is one of the most famous results in Graph Theory. It was conjectured by F. Guthrie in 1852, given a false proof by A. Kempe in 1879, had its false proof disproved in 1890, and then remained a conjecture until 1976, when it was proved by K. Appel and W. Haken using a computer program that required 1200 hours of computer time. In contrast to the 4CT, it is much easier to show that any map may be 6-colored. In this talk, we will discuss the map-coloring game, which was invented by S. Brams over 30 years ago: Alice wants to color a planar map. She and Bob alternately choose a region to color, using a set of k different colors. Alice wins if the coloring is completed, and Bob wins if it cannot be completed. The game chromatic number of a map is the smallest k such that Alice can win the game on the map. It is fairly easy to show that the game chromatic number of any planar map is less than or equal to 3044, but the largest known value of the game chromatic number is 8. Will it take another 90 years to find the best bound? Lunch will be served!!

Get Directions
Event Date
Event Time