Pearls in Graph Theory A Comprehensive Introduction

by Hartsfield, Nora; Ringel, Gerhard

• ISBN13: 9780486432328
• ISBN10: 0486432327
• Format: Paperback
• Copyright: 2003-12-29
• Publisher: Dover Publications

Summary

"Innovative introductory text . . . clear exposition of unusual and more advanced topics . . . Develops material to substantial level."--American Mathematical Monthly"Refreshingly different . . . an ideal training ground for the mathematical process of investigation, generalization, and conjecture leading to the discovery of proofs and counterexamples."--American Mathematical Monthly" . . . An excellent textbook for an undergraduate course."--Australian Computer JournalA stimulating view of mathematics that appeals to students as well as teachers, this undergraduate-level text is written in an informal style that does not sacrifice depth or challenge. Based on 20 years of teaching by the leading researcher in graph theory, it offers a solid foundation on the subject. This revised and augmented edition features new exercises, simplifications, and other improvements suggested by classroom users and reviewers. Topics include basic graph theory, colorings of graphs, circuits and cycles, labeling graphs, drawings of graphs, measurements of closeness to planarity, graphs on surfaces, and applications and algorithms. 1994 ed.

Author Biography

Nora Hartsfield: Western Washington University Gerhard Ringel: University of California

Table of Contents

Foreword to the Revised Edition	vii
Foreword	ix
Chapter 1. Basic Graph Theory
1.1 Graphs and Degrees of Vertices	1	(12)
1.2 Subgraphs, Isomorphic Graphs	13	(4)
1.3 Trees	17	(6)
Chapter 2. Colorings of Graphs
2.1 Vertex Colorings	23	(8)
2.2 Edge Colorings	31	(4)
2.3 Decompositions and Hamilton Cycles	35	(8)
2.4 More Decomposition	43	(6)
Chapter 3. Circuits and Cycles
3.1 Eulerian Circuits	49	(9)
3.2 The Oberwolfach Problem	58	(7)
3.3 Infinite Lattice Graphs	65	(5)
Chapter 4. Extremal Problems
4.1 A Theorem of Turan	70	(7)
4.2 Cages	77	(4)
4.3 Ramsey Theory	81	(6)
Chapter 5. Counting
5.1 Counting 1-Factors	87	(7)
5.2 Cayley's Spanning Tree Formula	94	(6)
5.3 More Spanning Trees	100	(4)
Chapter 6. Labeling Graphs
6.1 Magic Graphs and Graceful Trees	104	(10)
6.2 Conservative Graphs	114	(11)
Chapter 7. Applications and Algorithms
7.1 Spanning Tree Algorithms	125	(8)
7.2 Matchings in Graphs, Scheduling Problems	133	(7)
7.3 Binary Trees and Prefix Codes	140	(9)
Chapter 8. Drawings of Graphs
8.1 Planar Graphs	149	(7)
8.2 The Four Color Theorem	156	(8)
8.3 The Five Color Theorem	164	(4)
8.4 Graphs and Geometry	168	(11)
Chapter 9. Measurements of Closeness to Planarity
9.1 Crossing Number	179	(11)
9.2 Thickness and Splitting Number	190	(7)
9.3 Heawood's Empire Problem	197	(11)
Chapter 10. Graphs on Surfaces
10.1 Rotations of Graphs	208	(9)
10.2 Planar Graphs Revisited	217	(8)
10.3 The Genus of a Graph	225	(16)
References	241	(4)
Index	245