Graph coloring

[tad white]

The following result must certainly appear in the vast literature:

----------
Let P(q) denote the chromatic polynomial of a graph G. For each
n>=0, let a_n denote the number of inequivalent colorings of G
with _exactly_ n colors, where equivalence is induced by the action
of the symmetric group S_n on the n colors.

E.g. if G is the graph

o---o---o

then a_0=a_1=0; a_2=1 (the colorings 1---2---1 and 2---1---2 are
equivalent); and a_3=1 (the eqv. class of 1---2---3.)

Now express P(q) in terms of "falling-powers": that is, as a
linear combination of q_n^s, where q_n=q(q-1)...q(q-n+1).
Then a_n is the coefficient of q_n.

e.g. For G above, P(q) = q(q-1)^2 = q(q-1)(q-2) + q(q-1).
----------

Does anyone have any pointers to this? (I know how to prove it,
I just want to be able to cite it, if it is around somewhere.)

Thanks in advance! -- Tad
--

/**************************************************************\
* Tad White UCR Dept. of Mathematics *
* tad...@ucrmath.ucr.edu Riverside, CA 92521 *

[Dr. C.D. Wright]

I think you'll find that the result you quote drops out directly
from the usual addition/contraction derivation of the chromatic
polynomial. In that you are effectively constructing the inequivalent
(=n)-colourings, and you end up with complete graphs at the end.
You then write your polynomial as the sum of the polynomials of
the complete graphs, and there it is.

There is similar work done that involves an extension to the chromatic
polynomial and in which evaluations do not give only the number of
colourings, but the "shape" of the colourings as well. The polynomial
is over a ring and the evaluations are elements of the ring that
somehow capture the essential information about the colour partitions
induced. The main reference to this is

N. Ray and C. Wright (1988) Colourings and partition types:
a generalised chromatic polynomial, Ars Comb. 25B, 277-286.

A more lucid, complete and rigorous treatment is given in my PhD
thesis - "Combinatorial Algorithms", Cambridge University.
If you want more details, let me know.

-------------------- Original Article follows ---------------------

tad white (tad...@drysdale.ucr.edu) wrote:
: The following result must certainly appear in the vast literature: