The Peterson recurrence formula for the chromatic discriminant of a graph

摘要

The absolute value of the coefficient of q in the chromatic polynomial of a graph G is known as the chromatic discriminant of G and is denoted alpha(G). There is a well known recurrence formula for alpha(G) that comes from the deletion-contraction rule for the chromatic polynomial. In this paper we prove another recurrence formula for alpha(G) that comes from the theory of Kac- Moody Lie algebras. We start with a brief survey on many interesting algebraic and combinatorial interpretations of alpha(G). We use two of these interpretations (in terms of acyclic orientations and spanning trees) to give two bijective proofs for our recurrence formula of alpha(G).