[Home ] [Title List ] [Tables of Contents and Reviews] [Ordering Information]

Graph Theory: A Development from the 4-Color Problem, by Martin Aigner

Translated into English from the 1984 German edition (B.G. Teubner: Stuttgart), with the assistance of the author. The guiding theme is the influence of the 4-color problem on the evolution of graph theory. There are ten chapters, each with many exercises of varying difficulty. Zentralblatt says: "Die Darstellung ist lebendig, didaktisch geschickt und engagiert."

TABLE OF CONTENTS

1. TRANSLATOR'S PREFACE
   
2. FOREWORD
   
3. PART I: INTRODUCTION
   
   1. Origin and "Solution"
      4-Color Problem, Graph, Map, Coloring, Euler Formula, the Erroneous "Solution" of Kempe, Tait's 3-Color Theorem, Exercises.
   2. Errors and Hopes
      Kempe's Error, 5-Color Theorem, Closed Surfaces, Euler-Poincare Formula, Heawood's Color Theorem, Duality of Graphs and Maps, Exercises.
   3. New Beginnings
      Arithmetization of the Problem by Heawood, Veblen's Geometric Ideas, Euler Graphs, Birkhoff and the Counting of Colorings, Factorization of Graphs, Petersen's Theorem, Hamiltonian Circuits, Polytopal Graphs, Exercises.
4. PART II: THEME
   
   1. Planarity
      Connectivity of Graphs, Menger's Theorem, the Characterization of Planar Graphs by Kuratowski, Whitney and MacLane, Duality, Genus of Graphs, Crossing Number, Exercises.
   2. Coloring
      Chromatic Number and Chromatic Index, the Theorems of brooks and Vizing, Critical Graphs, Hadwiger's Conjecture, Chromatic Polynomial, Triangulations, Exercises.
   3. Factorization
      Matching in Bipartite Graphs, the Theorems of Konig and Hall, Transversals of Set Systems, Doubly Stochastic Matrices, Latin Squares, the Tutte Theorem on the Existence of 1-Factors, Exercises.
   4. Hamiltonian Circuits
      Theorems of Whitney and Tutte on Hamiltonian Plane Graphs, Necessary Conditions, Hamiltonian Closure and the Chvatal Theorem \, Extremal Problems in Graphs, the Theorems of Turan and Ramsey, Exercises.
   5. Matroids
      Axiomatic Descriptions, Duality, Polygon Matroid and BOnd Matroid of Graphs, Edmond's Theorem, Cycles and Cocycles, Chain Groups, Minors, Irreducible Groups, the Geometric Ideas of Tutte, Exercises.
5. PART III: FINALE
   
   1. Back to the Beginning
      Two Ideas: Reducibillity and Unavoidability, The Birkhoff Theorems, D-Reducibility, Obstructions, Unavoidable Sets and the Method of Unloading, Exercises.
   2. Solution and Problem
      Geographically Good Configurations, Probabilistic Aspects, Reducibility Conjecture, Residues, Chromodendra, Plausibility Considerations on Unavoidability, the Final Program of Appel and Haken, the Solution, Criticism and Prospects, Exercises.
6. BIBLIOGRAPHY
   
7. LIST OF SYMBOLS
   
8. INDEX
   

Back to Top

[Home ] [Title List ] [Tables of Contents and Reviews] [Ordering Information]