The search for chromatically unique graphs

Abstract

The number of vertex-colourings of a simple graph G in not more than λ colours is a polynomial in λ. This polynomial, denoted by P(G, λ), is called the chromatic polynomial of G. A graph G is said to be chromatically unique, in short χ-unique, if H ≅ G for any graph H with P(H, λ) = P(G, λ). Since the appearance of the first paper on χ-unique graphs by Chao and Whitehead in 1978, various families of and several results on such graphs have been obtained successively, especially during the last five years. It is the aim of this expository paper to give a survey on most of the works done on χ-unique graphs. A number of related problems and conjectures are also included. © 1990 Springer-Verlag.