A Survey of Graph Polynomials Related to the Chromatic Polynomial

Abstract

Introduced by Birkhoff in 1912 to study the four-color conjecture, the chromatic polynomial has become one of the most extensively studied graph polynomials. It is closely connected to the Tutte polynomial through specialization, to the characteristic polynomial of the associated graphic matroid, and to the flow polynomial through planar duality. It has also inspired several related polynomials, including the $\sigma$-polynomial, the $w$-polynomial, and the $\tau$-polynomial. This survey examines these relationships, illustrated in Figure 1, and reviews the main results.

arXiv comment66 pages, more than 13 figures and 114 references