The next Math/CS Chat will be held on Thursday, October 6th at Noon in Tome 115. Gary Haggard, Professor of Computer Science at Bucknell University, will present "Chromatic Polynomials Blending Mathematics & Computer Science". Free pizza!
Abstract: 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. Althought 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 give us insight into the nature of these 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 computer chromatic polynomials will be explained. A theorem suggested by the results of a computation will be shown.