A Generalised Bad Colouring Polynomial
by
Geoff Whittle
Victoria University
Coauthors: Dominic Welsh

A bad edge of a vertex coloured graph is an edge whose endpoints both have the same colour. The so called ``bad colouring'' polynomial of a graph is a two variable polynomial that enables one to determine, for any \lambda and k, the number of \lambda colourings of the graph with exactly k bad edges. This polynomial is intimately related to the Tutte polynomial of the graph. The talk discusses an extension of the bad colouring polynomial to more general classes of structures. Evaluations of this polynomial contain a surprising amount of combinatorial information. For example, one can associate a generalised bad colouring polynomial with any collection S of subspaces of a vector space over a finite field. For any j and k, one can use the bad colouring polynomial to obtain the number of rank-j subspaces of the vector space that contain exactly k members of S.

Date received: June 1, 1998

Copyright © 1998 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cabd-26.