Presented by: 
Gary Haggard (Bucknell University)
Mon 2 Sep, 2:00 pm - 2:45 pm
Otto Hirschfeld Building 81-214

Coloring graphs has intrigued mathematicians since the 4-Color Conjecture was first posed. One major attempt to confirm this conjecture in the 20th century involved a new mathematical structure called a chromatic polynomial. Although this structure did not yield a solution, it has taken on a life of its own as an important way to study graph coloring.

The use of mathematics and computer science blend together in the study of chromatic polynomials. The mathematics gives us insight into the nature of these polynomials and computer science gives us a way to explore nontrivial examples not amenable to hand calculation.

Some of the open questions about these polynomials will be explored including when a polynomial is a chromatic polynomial and when is a chromatic polynomial the chromatic polynomial of exactly one graph.

The currently fastest algorithm for computing chromatic polynomialswill be explained. A theorem suggested by the results of a computation will be shown.