Dong F.M., Koh K.M., Teo K.L. Chromatic Polynomials and Chromaticity of Graphs

Издательство World Scientific, 2005, -380 pp.For a century, one of the most famous problems in mathematics was to prove the four-colour theorem. This has spawned the development of many useful tools for solving graph colouring problems. In a paper in 1912, Birkhoff proposed a way of tackling the four-colour problem by introducing a function P(M,λ), defined for all positive integers λ, to be the number of proper λ-colourings of a map M. It turns out that P(M,λ) is a polynomial in A, called the chromatic polynomial of M. If one could prove that P(M,4) 0 for all maps M, then this would give a positive answer to the four-colour problem. The polynomial P(M,λ) is defined for all real and complex values of λ. It was hoped that many useful tools from algebra and analysis could be used to find or estimate the roots of the polynomial and hence lead to the resolution of the problem.
The notion of a chromatic polynomial was later generalized to that of an arbitrary graph by Whitney A932), who established many fundamental results for it. In 1946, Birkhoff and Lewis obtained results concerning the distribution of real roots of chromatic polynomials of planar graphs and conjectured that these polynomials have no real roots greater than or equal to four. The conjecture remains open.
In 1968, Read aroused new interest in the study of chromatic polynomials with his well referenced introductory article on the subject. He asked if it is possible to find a set of necessary and sufficient algebraic conditions for a polynomial to be the chromatic polynomial of some graph. For example, it is true that the chromatic polynomial of a graph determines the numbers of vertices and edges and that its coefficients are integers which alternate in sign. Read observed that the absolute values of the coefficients appear to form a unimodal sequence.
Read asked: What is a necessary and sufficient condition for two graphs to be chromatically equivalent; that is, to have the same chromatic polynomial? In particular, Chao and Whitehead Jr. A978) defined a graph tobe chromatically unique if no other graphs share its chromatic polynomial. They found several families of such graphs. Since then many invariants under chromatic equivalence have been found and various families of and results on such graphs have been obtained successively. The question of chromatic equivalence and uniqueness is termed the chromaticity of graphs. This remains an active area of research.
Although Birkhoff's hope of using the chromatic polynomial to prove the four-colour theorem was not borne out, it has attracted a steady stream of attention through the years, especially concerning the location of its roots. More recently, Thomassen discovered a relation between hamiltonian paths and the roots of the chromatic polynomial. There has also been an influx of new ideas from statistical mechanics due to the recent discovery of a connection to the Potts Model in Physics.
This book is divided into three main parts, after providing a chapter on the basic concepts and terminology of graphs and a list of notation that are needed and used in the book. Part one covers the first three chapters. It is devoted in greater detail than the other two to the rudiment of chromatic polynomials; their basic properties are derived, and some practical methods for computing them are given. Furthermore, we provide several ways of constructing chromatically equivalent graphs; characterize chromatically unique graphs that are disconnected and those with connectivity
1. Further results on chromatic equivalence classes of families of graphs are mentioned.
Part two, which consists of eight chapters from Chapter 4 to Chapter 11, deals specifically with the chromaticity of multi-partite graphs, subdivisions of graphs, and members of those families whose colour classes have nice structures. By expanding a chromatic polynomial of a graph in terms of falling factorials, we construct a polynomial, called the adjoint polynomial of the graph. We study several invariants of this polynomial and roots of some particular ones. It was found that this polynomial was particularly useful in determining the chromaticity of graphs whose complements are of simpler structure. We also mention some related polynomials.
The last part of the book covers the last four chapters and is concerned with the distribution of roots of the chromatic polynomials both on the real line and in the complex plane. In particular, we study those chromatic polynomials that possess only integral roots. Furthermore, we study bounds and inequalities of the chromatic polynomials of families of graphs.
The Number of λ-Colourings and Its Enumerations.
Chromatic Polynomials.
Chromatic Equivalence of Graphs.
Chromaticity of Multi-Partite Graphs.
Chromaticity of Subdivisions of Graphs.
Graphs in Which any Two Colour Classes Induce a Tree (I).
Graphs in Which any Two Colour Classes Induce a Tree (II).
Graphs in Which All but One Pair of Colour Classes Induce Trees (I).
Graphs in Which All but One Pair of Colour Classes Induce Trees (II).
Chromaticity of Extremal 3-Colourable Graphs.
Polynomials Related to Chromatic Polynomials.
Real Roots of Chromatic Polynomials.
Integral Roots of Chromatic Polynomials.
Complex Roots of Chromatic Polynomials.
Inequalities on Chromatic Polynomials.