Polynomial graph invariants and the KP hierarchy
We prove that the generating function for the symmetric chromatic polynomial of all simple graphs is (after an appropriate scaling change of variables) a linear combination of one-part Schur polynomials. This statement immediately implies that it is also a tau-function of the Kadomtsev–Petviashvili integrable hierarchy of mathematical physics. Moreover, we describe a large family of polynomial graph invariants leading to the same tau-function. In particular, we introduce the Abel polynomial for graphs and show this for its generating function. The key point here is a Hopf algebra structure on the space spanned by graphs and the behavior of the invariants on its primitive space.