Revisiting Chromatic Polynomials of Some Sequences of Graphs

Abstract

The chromatic polynomial of a graph \(\Gamma\), \(C(\Gamma; \lambda)\), is the polynomial in \(\lambda\) which counts the number of distinct proper vertex \(\lambda\)-colorings of \(\Gamma\), given \(\lambda\) colors. By applying the addition-contraction method, chromatic polynomials of some sequences of \(2\)-connected graphs satisfy a number of recursive relations. We will show that by knowing the chromatic polynomial of a few small graphs, the chromatic polynomial of each of these sequences can be computed by utilizing either matrices or generating functions.