Chromatic invariants for finite graphs: Theme and polynomial variations

AbstractThe value Px(q) at an integer q ⩾1 of the chromatic polynomial of a finite graph X is the number of morphisms from X to the q-cliqueKq. Generalized chromatic invariants of X are obtained by counting morphisms from X to the qth graph of a given sequence Y∗ = (Yq)q ⩾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