The Computation and Basic Properties of Chromatic Polynomials
by
K L Teo
Massey University

Let G be a graph and V(G) its vertex set. A k-colouring of G is a mapping f from V(G) into the set 1, 2, ..., k such that f(u) is not equal to f(v) if u and v are adjacent in G. Let P(G, k) be the number of distinct k-colourings of G. Then P(G, k) is a polynomial in k, called the chromatic polynomial of G. In this talk we will present ways for computing the chromatic polynomials. Some basic properties of the chromatic polynomials will be dicussed.

Date received: June 25, 1998