Five-Coloring Plane Graphs



Friday, 19 October 2012, 15:00 to 16:30


  • A-212 (STCS Seminar Room)


The four-color theorem states that it is always possible to color the regions of a plane map with four colors such that regions that share a boundary receive different colors. This theorem was proven in 1976 by Appel and Haken. The proof of the theorem required the calculating power of computers. Although I have a good computer (probably more powerful than the computer that was used in the original proof), we will not try to prove the four-color theorem. We will be modest and prove that we can color a plane map with five colors.