Hall 123

An exposition to Chromatic Polynomials

GArun Kumar

IMSc, Chennai

In this talk, I will introduce the theory of Chromatic Polynomials. I will define the colouring of a graph G and prove that the number of ways of coloring a graph using q colours is a polynomial in q. This polynomial is known as the chromatic polynomial of the graph G. I will derive some of their important properties. Also I will list some practical methods for computing the chromatic polynomials and will compute them for some well known class of graphs.
In the second half of the talk, I will show the connection between the chromatic polynomials and the free partially commutative Lie algebras by using the free partially commutative monoids and Lyndon words . No prerequisite of Lie algebras and Graph theory will be needed.