Abstract by Rebekah Bassett
Coloring the Map of Utah
The “four color theorem” asserts that any planar graph is four colorable. Let p(G,r) be the number of ways to color a graph G with r colors. p(G,r) is a monic polynomial of degree |V(G)| with integer coefficients and is called the chromatic polynomial. It is surprising that no one has computed this polynomial for real world graphs, like the graph of the map of the counties of Utah. The four of us have done that in this project.
My part of the presentation will begin with two specific theorems that aided our efforts in finding the chromatic polynomial for more complicated graphs. For example, we found the chromatic polynomial of two interlocking wheels by subtracting and moding edges systematically. After computing the polynomial 3 different ways, multiple checks prove that our polynomial is correct. Moreover, one of those ways led us to invent a theorem for the chromatic polynomial of interlocking wheels of any size, and the application of this new theorem resulted in finding the chromatic polynomial of the counties of Utah, a graph with 29 vertices.