
06439643
j
2015d.00810
Kehle, Paul
Colorful polynomial explorations.
Consortium 106, 3037 (2014).
2014
COMAP (Consortium for Mathematics and Its Applications), Bedford, MA
EN
K30
graph theory
planar graphs
mapcolouring problems
chromatic theory
vertex colourings of a graph
cycle graphs
chromatic polynomials
roots
edgeaddition contraction principle
edgedeletion contraction principle
exploratory learning
student activities
chromatic uniqueness
Zbl 0331.05106
Zbl 1030.05041
From the text: Since the work of {\it K. Appel} and {\it W. Haken} [Bull. Am. Math. Soc. 82, 711712 (1976; Zbl 0331.05106)], we have known that no map will require more than four colors if countries that share a border must receive different colors. Their proof finally resolved a conjecture first made in 1852. The history of the fourcolor theorem is fascinating and very accessible in {\it R. Wilson}'s [Four colors suffice. How the map problem was solved. Princeton, NJ: Princeton University Press (2002; Zbl 1030.05041)]. To work on a mapcoloring problem we use a graph in which vertices represent the countries, and we join two vertices by an edge if the two countries share a border. The resulting graph will be a planar graph, meaning that it can be drawn so that no edges cross one another. A solution to a mapcoloring problem is a proper vertex coloring of a graph: vertices joined by an edge are assigned different colors.