Chromatic polynomials and chromaticity of graphs.

*(English)*Zbl 1070.05038
Singapore: World Scientific Publishing (ISBN 981-256-317-2/hbk; 981-256-383-0/pbk). xxvii, 356 p. (2005).

This nice book is devoted to the recent developments in the theory of chromatic polynomials. It is divided into three main parts, after providing a chapter on the basic concepts and terminology of graphs and a list of notation used in the book.

Part one covers the first three chapters: The number of \(\lambda \)-colourings and its enumeration, Chromatic polynomials, Chromatic equivalence of graphs. It is devoted to the basic properties of chromatic polynomials, and to some practical methods for computing them. Several ways of constructing chromatically equivalent graphs and of characterizing chromatically unique graphs are given. Further results on chromatic equivalence classes of families of graphs are mentioned.

Part two, which consist of eight chapters: Chromaticity of multipartite and of subdivisions of graphs, Graphs in which any two color classes induce a tree, Graphs in which all but one pair of color classes induce trees, Chromaticity of extremal 3-colourable graphs, Polynomials related to chromatic polynomials, deals with the chromaticity of multipartite graphs, subdivisions of graphs, and members of those families whose colour classes have nice structures. Several invariants and roots of the adjoint polynomial are studied, this polynomial being useful in determining the chromaticity of graphs whose complements are of simpler structure. Some related polynomials are also mentioned.

The last part of the book covers the last four chapters: Real, integral and complex roots of chromatic polynomials, Inequalities on chromatic polynomials and is concerned with the distribution of roots of the chromatic polynomials both on the real line and in the complex plane in connection to the Potts model in physics. In particular, those chromatic polynomials that possess only integral roots are studied. Finally, there are studied bounds and inequalities for the chromatic polynomials of some families of graphs. The bibliography contains 402 titles.

The book is clearly written, well illustrated, and supplied with carefully designed exercises, it takes pleasure in using it as an graduate textbook or for independent study. It leads the reader to the frontiers of present research in the theory of chromatic polynomials and offers insight into some exciting developments.

Part one covers the first three chapters: The number of \(\lambda \)-colourings and its enumeration, Chromatic polynomials, Chromatic equivalence of graphs. It is devoted to the basic properties of chromatic polynomials, and to some practical methods for computing them. Several ways of constructing chromatically equivalent graphs and of characterizing chromatically unique graphs are given. Further results on chromatic equivalence classes of families of graphs are mentioned.

Part two, which consist of eight chapters: Chromaticity of multipartite and of subdivisions of graphs, Graphs in which any two color classes induce a tree, Graphs in which all but one pair of color classes induce trees, Chromaticity of extremal 3-colourable graphs, Polynomials related to chromatic polynomials, deals with the chromaticity of multipartite graphs, subdivisions of graphs, and members of those families whose colour classes have nice structures. Several invariants and roots of the adjoint polynomial are studied, this polynomial being useful in determining the chromaticity of graphs whose complements are of simpler structure. Some related polynomials are also mentioned.

The last part of the book covers the last four chapters: Real, integral and complex roots of chromatic polynomials, Inequalities on chromatic polynomials and is concerned with the distribution of roots of the chromatic polynomials both on the real line and in the complex plane in connection to the Potts model in physics. In particular, those chromatic polynomials that possess only integral roots are studied. Finally, there are studied bounds and inequalities for the chromatic polynomials of some families of graphs. The bibliography contains 402 titles.

The book is clearly written, well illustrated, and supplied with carefully designed exercises, it takes pleasure in using it as an graduate textbook or for independent study. It leads the reader to the frontiers of present research in the theory of chromatic polynomials and offers insight into some exciting developments.

Reviewer: Ioan Tomescu (Bucureşti)