# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Modern graph theory. (English) Zbl 0902.05016
Graduate Texts in Mathematics. 184. New York, NY: Springer. xiii, 394 p. DM 68.00; öS 497.00; sFr. 62.00; £ 26.00; $34.95 (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.

##### MSC:
 05Cxx Graph theory
graph theory