Graphs & Digraphs, Fifth Edition: (Textbooks in Mathematics)

Continuing to provide a carefully written, thorough introduction, Graphs & Digraphs, Fifth Edition expertly describes the concepts, theorems, history, and applications of graph theory. Nearly 50 percent longer than its bestselling predecessor, this edition reorganizes the material and presents many new topics. New to the Fifth Edition New or expanded coverage of graph minors, perfect graphs, chromatic polynomials, nowhere-zero flows, flows in networks, degree sequences, toughness, list colorings, and list edge colorings New examples, figures, and applications to illustrate concepts and theorems Expanded historical discussions of well-known mathematicians and problems More than 300 new exercises, along with hints and solutions to odd-numbered exercises at the back of the book Reorganization of sections into subsections to make the material easier to read Bolded definitions of terms, making them easier to locate Despite a field that has evolved over the years, this student-friendly, classroom-tested text remains the consummate introduction to graph theory. It explores the subject’s fascinating history and presents a host of interesting problems and diverse applications.

Table of Contents:
Introduction to Graphs Graphs and Subgraphs Degree Sequences Connected Graphs and Distance Multigraphs and Digraphs Trees and Connectivity Nonseparable Graphs Trees Spanning Trees Connectivity and Edge-Connectivity Menger’s Theorem Eulerian and Hamiltonian Graphs Eulerian Graphs Hamiltonian Graphs Powers of Graphs and Line Graphs Digraphs Strong Digraphs Tournaments 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 Factorization Decomposition and Graceful Graphs Domination 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 Cages Ramsey Theory Hints and Solutions to Odd-Numbered Exercises Bibliography Index of Names Index of Mathematical Terms List of Symbols