Chromatic invariants for finite graphs: Theme and polynomial variations (Q1899442)

The value \(P_X (q)\) at an integer \(q \geq 1\) of the chromatic polynomial of a finite graph \(X\) is the number of morphisms from \(X\) to the \(q\)-clique \(K_q\). Generalized chromatic invariants of \(X\) are obtained by counting morphisms from \(X\) to the \(q\)-th graph of a given sequence \(Y_* = (Y_q)_{q \geq 1}\). We give criteria on \(Y_*\) for the corresponding invariant to be polynomial, to be a matroid invariant, and to give rise to recursive computations. We also investigate weighted extensions of chromatic invariants, and applications to signed graphs and links in 3-space. Most of our work is an investigation of several examples. Two open problems are formulated.