Modern graph theory.

*(English)*Zbl 0902.05016
Graduate Texts in Mathematics. 184. New York, NY: Springer. xiii, 394 p. (1998).

As the author indicated, this book is an outgrowth of an earlier book Graph Theory – An Introductory Course, but this book is far more extensive than the earlier book. The book is composed of 10 chapters entitled (1) Fundamentals, (2) Electrical networks, (3) Flows, connectivity and matching, (4) Extremal problems, (5) Colouring, (6) Ramsey theory, (7) Random graphs, (8) Groups, graphs and matrices, (9) Random walks on graphs, and (10) The Tutte polynomial.

The first half of the book deals with the more classical, elementary, and standard topics covered in an introductory book. It starts with the basics. The later chapters deal with more recent and deeper topics. The range of topics covered in this book is quite extraordinary. Recent work in random graphs, random walks in graphs, and topics on polynomials and knot theory are dealt with in some detail near the end of the book. The pace of the presentation is more deliberate in the beginning chapters with considerably more detail given and more examples are presented. The presentation pace continues to pick up as you move through the book. In general, the presentation is clear, formal, and detailed, but the pace is certainly brisk. One of the outstanding features of the book is the extensive number of interesting exercises that appear in each of the chapters. There is a total of nearly 650 exercises with at least 45 exercises for each of the chapters. They are partitioned into four categories \(-\), standard, \(+\), and \(++\) in increasing order of difficulty. Each chapter ends with some notes and some bibliographic information; however, the bibliographic information is not extensive. Any reader who works her/his way through this book will have a solid knowledge of the broad range of topics that comprise graph theory.

The first chapter on fundamentals deals with introducing basic concepts, notation, and fundamental structures. Paths, cycles, trees, planar graphs, Hamiltonian cycles and Eulerian circuits are all discussed. In the second chapter three seemingly separate (but related) topics are presented – basic concepts of electrical networks, the problem of partitioning a rectangle into a finite collection of squares of distinct sizes, and matrices and vector spaces associated with a graph. The third chapter deals with a classical and fundamental connectivity results in graph theory. In particular the max-flow min-cut theorem of Ford-Fulkerson for flows, various forms of Menger’s theorem, and Hall’s and Tutte’s theorems on matchings are presented. The fourth chapter deals with extremal graph theory. There is a thorough treatment of Turán type extremal theory (both the numbers and the structure) including the Erdős-Stone theorem and its consequences. Also, Szemerédi’s regularity lemma is presented along with some applications of this powerful tool. The fifth chapter on colourings presents the classical results on both vertex and edge colourings and more recent results on list colourings. Other topics in the chapter include the chromatic numbers of graphs embedded in surfaces, and perfect graphs. Ramsey theory is the general topic of the sixth chapter. More specifically, fundamental classical Ramsey theory results are surveyed and some selected generalized Ramsey theory and numbers are presented. Ramsey theory of integers, including infinite colourings, the Hales-Jewett function, and the van der Waerden function are considered. Included in this is the result of Shelah. The seventh chapter begins by describing some of the basic models for studying random graphs. The phase transition for common graphical properties and properties of almost all graphs are investigated. One section is devoted to Hamiltonian graphs. The eighth chapter is an introduction to algebraic graph theory. This includes the study of Cayley graphs and Schreier diagrams, and the application of matrix methods to graph problems. Applications of the study of strongly regular graph are given, and Pólya’s enumeration theorem is also presented. Using properties of electrical networks, elementary concepts and facts for random walks in graphs were introduced in the first part of chapter nine, and then important parameters, such as the (mean) hitting time, and (mean) commuting time are studied in the last part of the ninth chapter. The last chapter of the book is devoted to the Tutte polynomial. Basic properties of the Tutte polynomial are given, along with the introduction of some other forms and some applications of the polynomial. The chapter ends with a discussion of polynomials and knots.

The first half of the book deals with the more classical, elementary, and standard topics covered in an introductory book. It starts with the basics. The later chapters deal with more recent and deeper topics. The range of topics covered in this book is quite extraordinary. Recent work in random graphs, random walks in graphs, and topics on polynomials and knot theory are dealt with in some detail near the end of the book. The pace of the presentation is more deliberate in the beginning chapters with considerably more detail given and more examples are presented. The presentation pace continues to pick up as you move through the book. In general, the presentation is clear, formal, and detailed, but the pace is certainly brisk. One of the outstanding features of the book is the extensive number of interesting exercises that appear in each of the chapters. There is a total of nearly 650 exercises with at least 45 exercises for each of the chapters. They are partitioned into four categories \(-\), standard, \(+\), and \(++\) in increasing order of difficulty. Each chapter ends with some notes and some bibliographic information; however, the bibliographic information is not extensive. Any reader who works her/his way through this book will have a solid knowledge of the broad range of topics that comprise graph theory.

The first chapter on fundamentals deals with introducing basic concepts, notation, and fundamental structures. Paths, cycles, trees, planar graphs, Hamiltonian cycles and Eulerian circuits are all discussed. In the second chapter three seemingly separate (but related) topics are presented – basic concepts of electrical networks, the problem of partitioning a rectangle into a finite collection of squares of distinct sizes, and matrices and vector spaces associated with a graph. The third chapter deals with a classical and fundamental connectivity results in graph theory. In particular the max-flow min-cut theorem of Ford-Fulkerson for flows, various forms of Menger’s theorem, and Hall’s and Tutte’s theorems on matchings are presented. The fourth chapter deals with extremal graph theory. There is a thorough treatment of Turán type extremal theory (both the numbers and the structure) including the Erdős-Stone theorem and its consequences. Also, Szemerédi’s regularity lemma is presented along with some applications of this powerful tool. The fifth chapter on colourings presents the classical results on both vertex and edge colourings and more recent results on list colourings. Other topics in the chapter include the chromatic numbers of graphs embedded in surfaces, and perfect graphs. Ramsey theory is the general topic of the sixth chapter. More specifically, fundamental classical Ramsey theory results are surveyed and some selected generalized Ramsey theory and numbers are presented. Ramsey theory of integers, including infinite colourings, the Hales-Jewett function, and the van der Waerden function are considered. Included in this is the result of Shelah. The seventh chapter begins by describing some of the basic models for studying random graphs. The phase transition for common graphical properties and properties of almost all graphs are investigated. One section is devoted to Hamiltonian graphs. The eighth chapter is an introduction to algebraic graph theory. This includes the study of Cayley graphs and Schreier diagrams, and the application of matrix methods to graph problems. Applications of the study of strongly regular graph are given, and Pólya’s enumeration theorem is also presented. Using properties of electrical networks, elementary concepts and facts for random walks in graphs were introduced in the first part of chapter nine, and then important parameters, such as the (mean) hitting time, and (mean) commuting time are studied in the last part of the ninth chapter. The last chapter of the book is devoted to the Tutte polynomial. Basic properties of the Tutte polynomial are given, along with the introduction of some other forms and some applications of the polynomial. The chapter ends with a discussion of polynomials and knots.

Reviewer: R.Faudree (Memphis)

##### MSC:

05Cxx | Graph theory |