Home
Research
Teaching
Other
Fall 2008: Graph Theory 21-801
Class information
- Class meetings: MW 12:30pm - 1:50pm, Porter Hall A20A
- Office hours: TT 2:00pm-3:00pm
- Syllabus:
Resources (including text books that are free and legal to download)
- Graph
Theory by Reinhard Diestel
- Graph
Theory with Applications by J.A. Bondy and U.S.R. Murty
- Digraphs:
Theory, Algorithms and Applications by Jřrgen Bang-Jensen and
Gregory Gutin
- Algorithms
and Complexity by Herbert Wilf
- An Introduction to Graph Algorithms by Ute Loerch
- Graph Theory Resources (collected by Daniel Sanders)
- Open Problems (collected by Douglas West)
Software
- JGraphT - Java graph theory library (provided by by Barak Naveh and Contributors)
- LEDA - A Library of Efficient Data Types and Algorithms
- nauty - software for computing automorphism groups of graphs and digraphs (provided by Brendan McKay)
- plantri and fullgen are programs for generation of certain types of planar graph and digraphs (provided by Gunnar Brinkmann and Brendan McKay)
- Combinatorial data (provided by Brendan McKay)
| Course outline (to be updated during the term) | ||
| Date | Topic | Remarks |
| 8/25 |
Hall's Thm, König's Thm | |
| 8/27 |
Tutte's Thm | |
| 9/1 |
Labor Day - no classes | |
| 9/3 |
Gallai-Edmonds Structure Thm | |
| 9/8 |
Erdős & Pósa Thm | Problem Set 1 |
| 9/10 |
Gallai & Milgram Thm, Dilworth's Thm, Sperner's Thm | |
| 9/15 |
The structure of 2-connected graphs | |
| 9/17 |
The structure of 3-connected graphs | |
| 9/22 |
Menger's Thm | |
| 9/24 |
"Linking" | Problem Set 2 |
| 9/29 |
Planar graphs | |
| 10/1 |
Kuratowski's Thm | |
| 10/6 |
Cycle and cut spaces | |
| 10/8 |
MacLane's Thm, Introduction to Ramsey numbers | Problem Set 3 |
| 10/13 |
Planar Ramsey numbers | Steinberg-Tovey |
| 10/15 |
Midterm | |
| 10/20 |
Problem Session (Sep 19) | |
| 10/22 |
Brook's Thm, Erdős graph | Alon-Spencer Aigner-Ziegler |
| 10/27 |
4 and 5 Color Thm, NP-completeness of edge coloring | 4CT Holyer |
| 10/29 |
List coloring | Voigt |
| 11/3 |
Perfect graphs | Perfect Graph Thm |
| 11/5 |
Minors | Problem Set 4 |
| 11/10 |
Hajós' and Hadwiger's Conjectures | Erdős-Fajtlowicz |
| 11/12 |
Szemerédi's Regularity Lemma | Szemerédi Survey |
| 11/17 |
Szemerédi's Regularity Lemma (contd.), Blow-Up Lemma | Gowers |
| 11/19 |
Applications of SRL - Linear Ramsey numbers | Chvatal_et_al, Aigner |
| 11/24 |
Applications of SRL (contd.) - Erdős-Stone Thm | Problem Set 5, Gowers |
| 11/26 |
Thanksgiving break - no classes | |
| 12/1 |
Eigenvalues of graphs | |
| 12/3 |
Expander Mixing Lemma, Pseudorandomness, MAX-CUT problem | Survey |
| 12/8 |
Final | |