Math 381, Graph Theory
Spring 2013
Syllabus

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
• Chapter 4. Extremal Problems
  • 4.1. A Theorem of Turan
  • 4.2. Cages
  • Extra: Line Graphs (handout)
• Chapter 5. Counting
  • 5.2. Cayley's Spanning Tree Formula
  • 5.3. More Spanning Trees
  • Extra: The Matrix-Tree Theorem (handout)
• Chapter 6. Labeling Graphs
  • 6.1. Magic Graphs and Graceful Trees
• Chapter 7. Applications and Algorithms
  • 7.1. Spanning Tree Algorithms
• Chapter 8. Drawings of Graphs
  • 8.1. Planar Graphs
  • 8.2. The Four Color Theorem
  • 8.3. The Five Color Theorem
• Chapter 9. Measurements of Closeness to Planarity
  • 9.1. Crossing Number
  • 9.2. Thickness and Splitting Number
  • 9.3. Heawood's Empire Problem
• Chapter 10 and Extra. Graphs on Other Surfaces
  • Diagrams for the Torus, Double Torus, etc. (in class)
  • 10.3. The Genus of a Graph
    (Omit anything about "schemes", "maximal rotations", and "current graphs", and pp. 235-237.)