You are here

Graphs & Digraphs

Gary Chartrand, Linda Lesniak, and Ping Zhang
Chapman & Hall/CRC
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee considers this book essential for undergraduate mathematics libraries.

[Reviewed by
John T. Saccoman
, on

Gary Chartrand has influenced the world of Graph Theory for almost half a century. He has supervised more than a score of Ph.D. dissertations and written several books on the subject. The most widely-known of these texts, Graphs and Digraphs, was coauthored in earlier editions with former student Linda Lesniak, and they have added their frequent collaborator Ping Zhang as a coauthor in the most recent edition. The text has much to recommend it, with a clear exposition, and numerous challenging examples make it an ideal textbook for the advanced undergraduate or beginning graduate course.

The authors have updated their notation to reflect the current practice in this still-growing area of study. By the authors’ estimation, the 5th edition is approximately 50% longer than the 4th edition.

Among the changes in the 5th edition are three separate chapters for vertex, map and edge colorings, expanded coverage of domination, matchings and extremal graph theory. In addition, the new version contains sections on perfect graphs, cages and historical figures of graph theory.

In the section on historical figures of graph theory, the legendary Frank Harary, author of the second graph theory text ever produced, is one of the figures profiled. His book was the standard in the discipline for several decades. Chartrand, Lesniak and Zhang have produced a worthy successor.

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

Introduction to Graphs
Graphs and Subgraphs
Degree Sequences
Connected Graphs and Distance
Multigraphs and Digraphs

Trees and Connectivity
Nonseparable Graphs
Spanning Trees
Connectivity and Edge-Connectivity
Menger’s Theorem

Eulerian and Hamiltonian Graphs
Eulerian Graphs
Hamiltonian Graphs
Powers of Graphs and Line Graphs

Strong Digraphs
Flows in Networks

Graphs: History and Symmetry
Some Historical Figures of Graph Theory
The Automorphism Group of a Graph
Cayley Color Graphs
The Reconstruction Problem

Planar Graphs
The Euler Identity
Planarity versus Nonplanarity
The Crossing Number of a Graph
Hamiltonian Planar Graphs

Graph Embeddings
The Genus of a Graph
2-Cell Embeddings of Graphs
The Maximum Genus of a Graph
The Graph Minor Theorem

Vertex Colorings
The Chromatic Number of a Graph
Color-Critical Graphs
Bounds for the Chromatic Number
Perfect Graphs
List Colorings

Map Colorings
The Four Color Problem
Colorings of Planar Graphs
The Conjectures of Hajós and Hadwiger
Chromatic Polynomials
The Heawood Map-Coloring Problem

Matchings, Factorization, and Domination
Matchings and Independence in Graphs
Decomposition and Graceful Graphs

Edge Colorings
Chromatic Index and Vizing’s Theorem
Class One and Class Two Graphs
Tait Colorings
Nowhere-Zero Flows
List Edge Colorings and Total Colorings

Extremal Graph Theory
Turán’s Theorem
Ramsey Theory

Hints and Solutions to Odd-Numbered Exercises
Index of Names
Index of Mathematical Terms
List of Symbols