CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS

Abstract

The chromatic polynomial is characterized as the unique polynomial invariant of graphs, compatible with two interacting bialgebras structures: the first coproduct is given by partitions of vertices into two parts, the second one by a contraction-extraction process. This gives Hopf-algebraic proofs of Rota's result on the signs of coefficients of chromatic polynomials and of Stanley's interpretation of the values at negative integers of chromatic polynomials. We also consider chromatic symmetric functions and their noncommutative versions.