Abstract :

The chromatic polynomial $\chi_G(q)$ of a graph $G$ is the number of proper colourings of its vertices with $q$ colours. The commutation monoid, or trace monoid, associated to $G$ was defined by Cartier and Foata in 1969. One starts with the alphabet consisting of the vertices of $G$; the commutation monoid is the set of all words in this alphabet where two letters (vertices) are allowed to commute if there is no edge between them. I will explain what chromatic polynomials and commutation monoids have to do with each other. In particular, an interpretation of the coefficients of the chromatic polynomial in terms of the commutation monoid will be given. This point-of-view stems from Xavier Viennot's recently concluded lecture coursecommutations and heaps of pieces at IMSc.