You are here

Introduction to Graph Theory

Douglas B. West
Publisher: 
Prentice Hall
Publication Date: 
2001
Number of Pages: 
588
Format: 
Hardcover
Edition: 
2
Price: 
132.00
ISBN: 
9780130144002
Category: 
Textbook
BLL Rating: 

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

[Reviewed by
John T. Saccoman
, on
04/28/2011
]

Around twenty years ago, the late Frank Harary’s Graph Theory was the standard for all texts in the discipline. Well-written, inclusive, and with challenging exercises, this book was the one people in the field would reference in their research papers (“For all Graph Theoretic terminology not included here, we refer the reader to Harary”). While Harary’s text remains excellent, the text of choice among Graph Theorists seems to have become Douglas West’s Introduction to Graph Theory. With so many competing texts out there, why is West’s book becoming the standard?

For one thing, the book is very well written, and contains material that has become a part of the subject as it has evolved. For example, he includes a significant section on matrices associated with graphs, and a proof of Kirchhoff’s Matrix-Tree Theorem, which is covered in most competing texts. He even includes an alternate proof of the result at the book’s website (http://www.math.uiuc.edu/~west/igt/), which also includes errata and a reader poll on terminology for a promised third edition.

This book is an excellent reference for Graph Theory. The section on Hamiltonian Cycles is quite good, and the chapter on matchings and factors, is, well, unmatched. It includes comprehensive coverage of Hall’s Theorem and its consequences, as well as an optional section on dominating sets that leads to more challenging investigations. Network flows, colorings and connectivity are also given a full treatment. The final chapter, Chapter 8, covers some advanced topics that could be pursued further by graduate students, such as perfect graphs, matroids, and extremal graph theory topics such as Ramsey Theory.

West includes a particular encoding of his exercises, of which there are a rich collection. Exercises marked “(+) “ or “(–)” are, respectively, more difficult or less difficult than unmarked problems, while “(!)” problems are “especially valuable, instructive, or entertaining.” He does caution that “(+)” problems should not be assigned as homework in a typical undergraduate course. Finally, “(*)” problems are those that are from material in so-called “optional” sections of the text.

West includes a number of appendices, covering such topics as background material on mathematical proofs, computational complexity of algorithms, a glossary of terms, and copious references. In short, this is an excellent text for advanced undergraduate or beginning graduate students, and their professors.


John T. Saccoman is Professor of Mathematics at Seton Hall University in South Orange, NJ

1. Fundamental Concepts.

 

What Is a Graph? Paths, Cycles, and Trails. Vertex Degrees and Counting. Directed Graphs.



2. Trees and Distance.

 

Basic Properties. Spanning Trees and Enumeration. Optimization and Trees.



3. Matchings and Factors.

 

Matchings and Covers. Algorithms and Applications. Matchings in General Graphs.



4. Connectivity and Paths.

 

Cuts and Connectivity. k-connected Graphs. Network Flow Problems.



5. Coloring of Graphs.

 

Vertex Colorings and Upper Bounds. Structure of k-chromatic Graphs. Enumerative Aspects.



6. Planar Graphs.

 

Embeddings and Euler's Formula. Characterization of Planar Graphs. Parameters of Planarity.



7. Edges and Cycles.

 

Line Graphs and Edge-Coloring. Hamiltonian Cycles. Planarity, Coloring, and Cycles.



8. Additional Topics (Optional).

 

Perfect Graphs. Matroids. Ramsey Theory. More Extremal Problems. Random Graphs. Eigenvalues of Graphs.



Appendix A: Mathematical Background.


Appendix B: Optimization and Complexity.


Appendix C: Hints for Selected Exercises.


Appendix D: Glossary of Terms.


Appendix E: Supplemental Reading.


Appendix F: References.


Indices.