1007 Wescoe Hall

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".

- Slides (full version, 141 pages with lots of overlays)
- Handout (abbreviated version of the slides, 60 pages; typo on p.34 fixed - thanks, Gary!)
- A map of the USA you can color
- Wikipedia: Graph theory
- Wikipedia: The 4CT
- MacTutor History of Mathematics Archive: The 4CT
- Robin Thomas's 4CT page (including downloadable code and documentation for the Robertson-Sanders-Seymour-Thomas proof)

Jeremy Martin's home page

KU Department of Mathematics

*Last updated Thu 6/6/13 1:30 PM*