How many colors are required to color a map so that no two adjacent regions (say, Kansas and Missouri) are given the same color? It turns out that every map can be colored with at most four colors, a fact suspected to be true since 1852, but not confirmed until 1976 (with the aid of intensive computation, an unprecedented approach to research at the time). In the century-long attempt to solve the map-coloring problem, mathematicians have developed theories of unexpected power and beauty: for example, problems about optimal routing and scheduling (and even Sudoku puzzles!) can be expressed as graph coloring problems. This course will explore both the history and the mathematics of the four-color theorem, including its practical applications, the many failed attempts to solve the problem, the debate over the validity of computer-assisted proofs, and the theoretical research for which mathematician Maria Chudnovsky was recently awarded a Macarthur "genius grant".
Jeremy Martin's home page
KU Department of Mathematics
Last updated Thu 6/6/13 1:30 PM