CHROMATIC INVARIANTS FOR FINITE GRAPHS - THEME AND POLYNOMIAL VARIATIONS

The value P-x(q) at an integer q greater than or equal to 1 of the chr omatic 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 obtai ned by counting morphisms from X to the qth graph of a given sequence Y- = (Y-q)(q greater than or equal to 1). We give criteria on Y-* for the corresponding invariant to be polynomial, to be a matroid invaria nt, and to give rise to recursive computations. We also investigate we ighted extensions of chromatic invariants, and applications to signed graphs and links in 3-space. Most of our work is an investigation of s everal examples. Two open problems are formulated.