You are here

Extremal Graph Theory

Béla Bollobás
Publisher: 
Dover Publications
Publication Date: 
2004
Number of Pages: 
488
Format: 
Paperback
Price: 
29.95
ISBN: 
0-486-43596-2
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Sandra Kingan
, on
05/1/2004
]

Dover recently issued a reprint of this 1978 classic textbook on extremal graph theory. The book is suitable for someone who has had a first course in graph theory and is interested in getting deeper into the subject.

This area of graph theory was initiated by Turán with his 1941 result now well-known as Turán’s theorem. Subsequently, much of the founding work was done by Erdös and his coauthors. Turán proved that the number of edges in a graph with n vertices that has no subgraph isomorphic to the complete graph on k vertices is at most n2(k-2)/2(k-1). He also identified the graphs for which equality holds. Such graphs are called extremal graphs. This theorem has inspired many results with different graphs excluded as subgraphs, as induced subgraphs, or as minors. There are several generalizations of this result, the most famous one being the Erdös-Stone theorem.

The author’s interpretation of extremal graph theory is much broader than Turán type problems. He includes, for example, Ramsey type theorems, results on inequalities involving graph invariants, and results on cycles, colorings, matchings, coverings, and packings. The book is packed (no pun intended) with important theorems and the techniques are just as interesting as the results.

Graduate students interested in specializing in combinatorics and researchers in the field would find this book worth reading. It contains many results that could lead to new results. The reviewer obtained her first theorem by partially generalizing to binary matroids a 1963 theorem of G. A. Dirac in which he identified the extremal 3-connected graphs without two vertex disjoint cycles (Theorem 2.1, Chapter 3). A complete generalization remains an unsolved problem.

The interested reader may also want to take a look at a follow-up book by the same author called Extremal graph theory with emphasis on probabilistic methods. This book, published in 1986, contains several important results that appeared after 1978.


Sandra Kingan (srkingan@psu.edu) is assistant professor of mathematics at the Pennsylvania State University, Capital College.


1.Connectivity.
2.Matching.
3.Cycles.
4.The Diameter.
5.Colourings.
6.Complete Subgraphs.
7.Topological Subgraphs.
8.Complexity and Packing.
References.
Indexes.