| 1 |
Aug 17 |
Introduction; Bridges and definitions |
1.1 |
HW1 assigned. |
| 2 |
Aug 22 |
Cliques and Independent sets; important graphs; isomorphism |
1.1 |
- |
| 3 |
Aug 24 |
Decompositions; Petersen graph |
1.1 |
- |
| 4 |
Aug 29 |
Walks, trails, paths; components; cut-vertices and cut-edges |
1.2 |
- |
| 5 |
Aug 31 |
Bipartite graphs; characterization |
1.2 |
- |
| 6 |
Sep 5 |
Eulerian Circuits; Eulerian graph characterization |
1.2 |
- |
| 7 |
Sep 7 |
Decomposing G into trails; degree-sum formula; hypercubes |
1.2,1.3 |
HW1 due; HW2 assigned. |
| 8 |
Sep 12 |
Extremal Problems |
1.3 |
- |
| 9 |
Sep 14 |
No class: WVU--China Graph Theory and Combinatorics Workshop |
- |
- |
| 10 |
Sep 19 |
Turan numbers; Mantel's theorem |
1.3 |
- |
| 11 |
Sep 21 |
Degree sequences; Havel--Hakimi |
1.3 |
HW2 due; HW3 assigned. |
| 12 |
Sep 26 |
Directed graphs; deBruijn cycles |
1.4 |
- |
| 13 |
Sep 28 |
Trees: basic properties |
2.1 |
- |
| 14 |
Oct 3 |
Prufer codes; deletion--contraction |
2.1 |
- |
| 15 |
Oct 5 |
Midterm exam: coverage up to and including Sep 28 |
- |
HW3 due. Midterm (pdf) |
| 16 |
Oct 10 |
Deletion-contraction; Matchings |
2.2,3.1 |
- |
| 17 |
Oct 12 |
Augmenting paths; Hall's Theorem |
3.1 |
HW4 assigned. |
| 18 |
Oct 17 |
Vertex covers; Konig--Egervary Thm |
3.1 |
- |
| 19 |
Oct 19 |
Tutte's Theorem |
3.3 |
- |
| 20 |
Oct 24 |
Tutte's Theorem applications; connectivity |
3.3,4.1 |
- |
| 21 |
Oct 26 |
Edge connectivity |
4.1 |
HW5 assigned. |
| 22 |
Oct 31 |
Blocks; Block-cut point graph |
4.1 |
- |
| 23 |
Nov 2 |
Ear Decompositions |
4.2 |
- |
| 24 |
Nov 7 |
Menger's Theorem |
4.2 |
- |
| 25 |
Nov 9 |
Flows; Ford--Fulkerson Algorithm |
4.3 |
HW5 due. HW6 assigned. |
| 26 |
Nov 14 |
Vertex coloring; greedy coloring algorithm; interval graphs |
5.1 |
- |
| 27 |
Nov 16 |
Brooks's Theorem |
5.1 |
- |
| 28 |
Nov 28 |
Mycielski's Construction; Turan's Theorem |
5.2 |
HW7 assigned (as of Nov. 23). HW6 due. |
| 29 |
Nov 30 |
Erdos--Stone--Simonovits Thm (w/o proof); Hajos and Hadwiger Conjectures |
5.2 |
- |
| 30 |
Dec 5 |
Planar graphs: Kuratowski Thm; Euler's Formula |
6.1 |
HW7 due. |
| - |
Dec 12 |
Final Exam: Tue Dec 12, 8am to 10am |
- |
- |