zbMATH — the first resource for mathematics

Some topics in graph theory. (English) Zbl 0588.05002
London Mathematical Society Lecture Note Series, 108. Cambridge etc.: Cambridge University Press. VI, 230 p. £12.50; $ 24.95 (1986).
The introductory chapter of this book provides the necessary background for what follows. In chapter 2 the author is mainly concerned with critical graphs introduced by Vizing. A connected graph G with \(\chi '=\Delta (G)+1\) is said to be (chromatic index) critical if \(\chi '(G- e)<\chi '(G)\) for any edge e of G. By \(\chi\) ’(G) and \(\Delta\) (G) we mean the chromatic index and the maximum valency of G, respectively. Some applications of edge-colourings to vertex-colourings and to the reconstruction of Latin squares are also described here. Chapter 3 examines some interactions between graphs and groups. Probably the best known result in this chapter is Frucht’s theorem on the existence of graphs with a given automorphism group. The author also deals with asymmetric graphs and with the degree of asymmetry of such graphs. Some properties of vertex-transitive graphs (especially Cayley graphs) are discussed and then the author turns his attention to s-transitive cubic graphs. In chapter 4 the following two packing problems are treated: a dense packing of trees of different sizes into \(K_ n\) and a general packing of two graphs having small size. Finally, chapter 5 is devoted to the computational complexity of graph properties. Some parts of the text derive from author’s recent paper in Graph theory, Proc. 1st Southeast Asian Colloq., Singapore 1983, Lect. Notes Math. 1073, 35-54 (1984; Zbl 0552.05056). The intended readers of this book are graduate students and specialists of graph theory. The style of writing is clear and the monograph is carefully organized. Its use as an educational textbook is facilitated by many exercises and open problems at the end of each section.
{One minor mistake is found on pages 107 and 146. Interchanging the first name and the surname the author quotes B. Zelinka as Z. Bohdan.}
Reviewer: J.Sedláček

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science