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).

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
• Chapter 6. Labeling Graphs
  • 6.1. Magic Graphs and Graceful Trees
  • 6.2. Conservative Graphs
• 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
• MORE