Dichromatic polynomials of linear graphs

Abstract

The dichromatic polynomial of a graph (or the Tutte polynomial) is a polynomial function of two variables from which a large amount of important information about the graph may be obtained , including the chromatic polynomial and the complexity of the graph. Some properties of the Tutte polynomial and an algorithm for its computation are given.a recursive family of graphs is defined to be a family of graphs whose Tutte polynomials satisfy a homogeneous linear recurrence relation.The smallest possible order of such a recurrence relation is called the recursiveness of the family. The existence of such a recurrence relation enables us to consider the Tutte polynomials of large graphs. Some elementary properties of recursive families are found and two large classes of recursive families of graphs are defined. The proof that the families in these classes are recursive is constructive and the methods used are applied to some families from the two classes with small recursiveness. The problem of the location of the chromatic roots of a graph is considered in the light of the information thus gained and several conjectures are made.The most important of these is a generalisation of Brooks' theorem [6] and states that for a graph whose greatest valency is k the chromatic roots all have modulus not greater than k + 1. Much of the work may be generalised immediately to matroid theory and where this is so the appropriate results are stated.