You are here

Topological Graph Theory

Jonathan L. Gross and Thomas W. Tucker
Publisher: 
Dover Publications
Publication Date: 
2001
Number of Pages: 
361
Format: 
Paperback
Price: 
14.95
ISBN: 
9780486417417
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Michael Berg
, on
03/7/2013
]

The chromatic number for a graph is the smallest number of colors needed to color the graph’s vertices in such a way that no two adjacent vertices (i.e., vertices connected by an edge) have the same color. Probably the most famous topological problem along these lines is the four color problem, to the effect that a planar map is always four-colorable — represent the countries by vertices and the borders by edges, and then show that the chromatic number is never more than four. Appell and Haaken took care of this notorious problem in 1976.

(By the way, in her excellent biography, Hilbert, Constance Reid recounts a hilarious episode from Hermann Minkowsi’s life concerning this problem. Evidently Minkowski, who despite his precocity and brilliance was a modest man, succumbed one day to a certain hubris and announced to his class that the reason the four-color problem was unsolved was that only third-rate mathematicians had considered it: he, however, believed he could prove the conjecture and, then and there, set out to do so. Day after day, lecture after lecture, he worked at the board in his Göttingen classroom, waging battle, but all to no avail. Finally, one very stormy day, his entry into his classroom was followed by a titanic thunder-clap… Said Minkowski: “The gods are offended at my arrogance: my proof, too, is flawed.” And then he returned to the syllabus proper, which he had abandoned some days before.)

Well, next, the chromatic number of a surface is, by definition, the largest of the chromatic numbers of simplicial graphs embeddable in the surface, so it is part and parcel of the four-color problem that the chromatic number of a (topological) plane is 4. As far back as 1890 Philip Heawood established that the chromatic number of a surface is at most equal to what is now called “Heawood’s number”: [12(7+4924c)], where c is the Euler characteristic of the surface and [x] gives the greatest integer ≤ x. In other words, given the relationship between the Euler characteristic and the genus of a surface, if a surface has genus g, then, regardless of how many vertices an imbedded graph might have, its chromatic number is bounded above by [12(7+1+48g)]. The thrust of the four-color theorem is that for a plane (or the sphere), with g = 0, this number reduces to 4, and Heawood’s bound is actually attained: every planar map is 4-colorable.

The central overarching problem in this field is, or was, Heawood’s problem, which asks for the precise determination of chromatic numbers of surfaces other than the sphere (genus 0, Euler characteristic 2: the four-color theorem). Heawood’s problem as such was fully solved in 1968 by Ringel and Youngs in the following form: “except for the Klein bottle, which has chromatic number 6, the chromatic number of every surface equals the corresponding Heawood number,” namely, [12(7+4924c)]. As already noted above, the four-color problem was settled in 1976 by Appell and Haaken, in what actually turned into a bit of a controversy, given that they employed computer searches in their solution, opening another can of worms altogether, namely, the question of the reliability of programs used in mathematical proofs. But this is neither here nor there at the moment.

It is in any event obvious that the subject of graph theory, or, more the point, topological graph theory, is infinitely fascinating, straddling as it does a number of subjects such as combinatorics, geometry, low-dimensional topology, and coming equipped with a variety of problems, spanning a huge spectrum of sophistication from accessible examples to fodder for full-fledged research programs. Topological graph theory is pervaded by the extremely seductive and evocative quality of visualizability of many of its claims and results, and by a certain magic vis à vis inductive methods: it’s a fabulous place to start one’s mathematical adventures, and a fabulous place to remain, of course.

The book under review is a classic in the field, and must be part of every topological graph theorist’s library — no: it had better sit on every such scholar’s desk, not collecting dust on a shelf. It’s a relatively short book, at a little over 300 pages (not counting the long list of references, bibliography, and index), and is pretty densely packed with very good stuff. It reads very well, with many, many wonderful theorems presented with compact but complete proofs. There is a wealth of fine illustrations to be had, as well as excellent problem lists strewn throughout the book. Gross and Tucker divide their coverage into six chapters, and the first starts with introductory material, including combinatorial topology, and works its way up to the topic of planarity. The second chapter addresses voltage and hits covering spaces. Chapter three is about the embedding of graphs in surfaces, followed by chapter four which deals with embedding voltage and current graphs (something of an apotheosis of electricity, one might argue). Then chapter five expressly addresses map colorings. Finally things get unapologetically algebraic in the sixth chapter, dealing with the notion of the genus of a group. A cornucopia of cool and seductive mathematics.

Dover has done it again: another classic at the price of a lunch at the school cafeteria. But the fare in Topological Graph Theory is far more varied, far more nourishing, and of far greater quality as well as quantity. You can’t miss!


Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.

 

1.

 

Introduction
1.1 Representation of Graphs
  1.1.1 Drawings
  1.1.2 Incidence Matrix
  1.1.3 Euler's theorem on valence sum
  1.1.4 Adjacency Matrix
  1.1.5 Directions
  1.1.6 Graphs, maps, isomorphisms
  1.1.7 Automorphisms
  1.1.8 Exercises
1.2 Some important classes of graphs
  1.2.1 Walks, paths, and cycles; connectedness
  1.2.2 Trees
  1.2.3 Complete graphs
  1.2.4 Cayley graphs
  1.2.5 Bipartite graphs
  1.2.6 Bouquets of Circles
  1.2.7 Exercises
1.3 New graphs from old
  1.3.1 Subgraphs
  1.3.2 Topological representations, subdivisions, graph homeomorphisms
  1.3.3 Cartesian products
  1.3.4 Edge-complements
  1.3.5 Suspensions
  1.3.6 Amalgamations
  1.3.7 Regular quotients
  1.3.8 Regular coverings
  1.3.9 Exercises
1.4 Surfaces and imbeddings
  1.4.1 Orientable surfaces
  1.4.2 Nonorientable surfaces
  1.4.3 Imbeddings
  1.4.4 Euler's equation for the sphere
  1.4.5 Kuratowski's graphs
  1.4.6 Genus of surfaces and graphs
  1.4.7 The torus
  1.4.8 Duality
  1.4.9 Exercises
1.5 More graph-theoretic background
  1.5.1 Traversability
  1.5.2 Factors
  1.5.3 Distance, neighborhoods
  1.5.4 Graphs colorings and map colorings
  1.5.5 Edge operations
  1.5.6 Algorithms
  1.5.7 Connectivity
  1.5.8 Exercises
1.6 Planarity
  1.6.1 A nearly complete sketch of the proof
  1.6.2 Connectivity and region boundaries
  1.6.3 Edge contraction and connectivity
  1.6.4 Planarity theorems for 3-connected graphs
  1.6.5 Graphs that are not 3-connected
  1.6.6 Algorithms
  1.6.7 Kuratowski graphs for higher genus
  1.6.8 Other planarity criteria
  1.6.9 Exercises
2. Voltage Graphs and Covering Spaces
2.1 Ordinary voltages
  2.1.1 Drawings of voltage graphs
  2.1.2 Fibers and the natural projection
  2.1.3 The net voltage on a walk
  2.1.4 Unique walk lifting
  2.1.5 Preimages of cycles
  2.1.6 Exercises
2.2 Which graphs are derivable with ordinary voltages?
  2.2.1 The natural action of the voltage group
  2.2.2 Fixed-point free automorphisms
  2.2.3 Cayley graphs revisited
  2.2.4 Automorphism groups of graphs
  2.2.5 Exercises
2.3 Irregular covering graphs
  2.3.1 Schreier graphs
  2.3.2 Relative voltages
  2.3.3 Combinatorial coverings
  2.3.4 Most regular graphs are Schreier graphs
  2.3.5 Exercises
2.4 Permutation voltage graphs
  2.4.1 Constructing covering spaces with permutations
  2.4.2 Preimages of walks and cycles
  2.4.3 Which graphs are derivable by permutation voltages?
  2.4.4 Identifying relative voltages with permutation voltages
  2.4.5 Exercises
2.5 Subgroups of the voltage group
  2.5.1 The fundamental semigroup of closed walks
  2.5.2 Counting components of ordinary derived graphs
  2.5.3 The fundamental group of a graph
  2.5.4 Contracting derived graphs onto Cayley graphs
  2.5.5 Exercises
3. Surfaces and Graph Imbeddings
3.1 Surfaces and simplicial complexes
  3.1.1 Geometric simplicial complexes
  3.1.2 Abstract simplicial complexes
  3.1.3 Triangulations
  3.1.4 Cellular imbeddings
  3.1.5 Representing surfaces by polygons
  3.1.6 Pseudosurfaces and block designs
  3.1.7 Orientations
  3.1.8 Stars, links, and local properties
  3.1.9 Exercises
3.2 Band Decompositions and graph imbeddings
  3.2.1 Band decomposition for surfaces
  3.2.2 Orientability
  3.2.3 Rotation systems
  3.2.4 Pure rotation systems and orientable surfaces
  3.2.5 Drawings of rotation systems
  3.2.6 Tracing faces
  3.2.7 Duality
  3.2.8 Which 2-complexes are planar?
  3.2.9 Exercises
3.3 The classification of surfaces
  3.3.1 Euler characteristic relative to an imbedded graph
  3.3.2 Invariance of Euler characteristic
  3.3.3 Edge-deletion surgery and edge sliding
  3.3.4 Completeness of the set of orientable models
  3.3.5 Completeness of the set of nonorientable models
  3.3.6 Exercises
3.4 The imbedding distribution of a graph
  3.4.1 The absence of gaps in the genus range
  3.4.2 The absence of gaps in the crosscap range
  3.4.3 A genus-related upper bound on the crosscap number
  3.4.4 The genus and crosscap number of the complete graph K subscript 7
  3.4.5 Some graphs of crosscap number 1 but arbitrarily large genus
  3.4.6 Maximum genus
  3.4.7 Distribution of genus and face sizes
  3.4.8 Exercises
3.5 Algorithms and formulas for minimum imbeddings
  3.5.1 Rotation-system algorithms
  3.5.2 Genus of an amalgamation
  3.5.3 Crosscap number of an amalgamation
  3.5.4 The White-Pisanski imbedding of a cartesian product
  3.5.5 Genus and crosscap number of cartesian products
  3.5.6 Exercises
4. Imbedded voltage graphs and current graphs
4.1 The derived imbedding
  4.1.1 Lifting rotation systems
  4.1.2 Lifting faces
  4.1.3 The Kirchhoff Voltage Law
  4.1.4 Imbedded permutation voltage graphs
  4.1.5 Orientability
  4.1.6 An orientability test for derived surfaces
  4.1.7 Exercises
4.2 Branched coverings of surfaces
  4.2.1 Riemann surfaces
  4.2.2 Extension of the natural covering projection
  4.2.3 Which branch coverings come from voltage graphs?
  4.2.4 The Riemann-Hurwitz equation
  4.2.5 Alexander's theorem
  4.2.6 Exercises
4.3 Regular branched coverings and group actions
  4.3.1 Groups acting on surfaces
  4.3.2 Graph automorphisms and rotation systems
  4.3.3 Regular branched coverings and ordinary imbedded voltage graphs
  4.3.4 Which regular branched coverings come from voltage graphs?
  4.3.5 Applications to group actions on the surface S subscript 2
  4.3.6 Exercises
4.4 Current graphs
  4.4.1 Ringel's generating rows for Heffter's schemes
  4.4.2 Gustin's combinatorial current graphs
  4.4.3 Orientable topological current graphs
  4.4.4 Faces of the derived graph
  4.4.5 Nonorientable current graphs
  4.4.6 Exercises
4.5 Voltage-current duality
  4.5.1 Dual directions
  4.5.2 The voltage graph dual to a current graph
  4.5.3 The dual derived graph
  4.5.4 The genus of the complete bipartite graph K (subscript m, n)
  4.5.5 Exercises
5. Map colorings
5.1 The Heawood upper bound
  5.1.1 Average valence
  5.1.2 Chromatically critical graphs
  5.1.3 The five-color theorem
  5.1.4 The complete-graph imbedding problem
  5.1.5 Triangulations of surfaces by complete graphs
  5.1.6 Exercises
5.2 Quotients of complete-graph imbeddings and some variations
  5.2.1 A base imbedding for orientable case 7
  5.2.2 Using a coil to assign voltages
  5.2.3 A current-graph perspective on case 7
  5.2.4 Orientable case 4: doubling 1-factors
  5.2.5 About orientable cases 3 and 0
  5.2.6 Exercises
5.3 The regular nonorientable cases
  5.3.1 Some additional tactics
  5.3.2 Nonorientable current graphs
  5.3.3 Nonorientable cases 3 and 7
  5.3.4 Nonorientable case 0
  5.3.5 Nonorientable case 4
  5.3.6 About nonorientable cases 1, 6, 9, and 10
  5.3.7 Exercises
5.4 Additional adjacencis for irregular cases
  5.4.1 Orientable case 5
  5.4.2 Orientable case 10
  5.4.3 About the other orientable cases
  5.4.4 Nonorientable case 5
  5.4.5 About nonorientable cases 11, 8, and 2
  5.4.6 Exercises
6. The Genus of a Group
6.1 The genus of abelian groups
  6.1.1 Recovering a Cayley graph from any of its quotients
  6.1.2 A lower bound for the genus of most abelian groups
  6.1.3 Constructing quadrilateral imbeddings for most abelian groups
  6.1.4 Exercises
6.2 The symmetric genus
  6.2.1 Rotation systems and symmetry
  6.2.2 Reflections
  6.2.3 Quotient group actions on quotient surfaces
  6.2.4 Alternative Cayley graphs revisited
  6.2.5 Group actions and imbeddings
  6.2.6 Are genus and symmetric genus the same?
  6.2.7 Euclidean space groups and the torus
  6.2.8 Triangle groups
  6.2.9 Exercises
6.3 Groups of small symmetric genus
  6.3.1 The Riemann-Hurwitz equation revisited
  6.3.2 Strong symmetric genus 0
  6.3.3 Symmetric genus 1
  6.3.4 The geometry and algebra of groups of symmetric genus 1
  6.3.5 Hurwitz's theorem
  6.3.6 Exercises
6.4 Groups of small genus
  6.4.1 An example
  6.4.2 A face-size inequality
  6.4.3 Statement of main theorem
  6.4.4 Proof of theorem 6.4.2: valence d = 4
  6.4.5 Proof of theorem 6.4.2: valence d = 3
  6.4.6 Remarks about Theorem 6.4.2
  6.4.7 Exercises
  References
  Bibliography
  Supplementary Bibliography
  Table of Notations
  Subject Index