A Contribution to the Theory of Chromatic Polynomials

Abstract

SummaryTwo polynomials θ(G, n) and ϕ(G, n) connected with the colourings of a graph G or of associated maps are discussed. A result believed to be new is proved for the lesser-known polynomial ϕ(G, n). Attention is called to some unsolved problems concerning ϕ(G, n) which are natural generalizations of the Four Colour Problem from planar graphs to general graphs. A polynomial χ(G, x, y) in two variables x and y, which can be regarded as generalizing both θ(G, n) and ϕ(G, n) is studied. For a connected graph χ(G, x, y) is defined in terms of the “spanning” trees of G (which include every vertex) and in terms of a fixed enumeration of the edges.