Department of Mathematical Sciences

Binghamton University

Math 381, Graph Theory

Spring 2004

Textbook

Nora Hartsfield and Gerhard Ringel, Pearls in Graph Theory, third edition (Dover, 2003).
(Essentially the same as the second edition, Academic Press, 1994.)

Topics

• Chapter 1. Basic Graph Theory
  • 1.1. Graphs and Degrees of Vertices
  • 1.2. Subgraphs, Isomorphic Graphs
  • 1.3. Trees
• Chapter 2. Colorings of Graphs
  • 2.1. Vertex Colorings
  • 2.2. Edge Colorings
  • 2.3. Decompositions and Hamilton Cycles
  • 2.4. More Decomposition
• Chapter 3. Circuits and Cycles
  • 3.1. Eulerian Circuits
  • 3.2. The Oberwohlfach Problem
  • 3.3. Infinite Lattice Graphs
• Chapter 4. Extremal Problems
  • 4.1. A Theorem of Turan
  • 4.2. Cages
• Chapter 8. Drawings of Graphs
  • 8.1. Planar Graphs
  • 8.2. The Four Color Theorem
  • 8.3. The Five Color Theorem
  • 8.4. Graphs and Geometry
• Chapter 9. Measurements of Closeness to Planarity
  • 9.1. Crossing Number
  • 9.2. Thickness and Splitting Number
  • 9.3. Heawood's Empire Problem