1 1/19We: introduction (overview of topics)
Chapter 6: Elementary Structural Concepts
2 1/21Fr: Matrix Tree Theorem, Matrix Arborescence Theorem, counting Eulerian circuits
3 1/24Mo: graceful labelings (hypercubes), T-decomposition (girth vs diameter)
4 1/26We: graph packing (Sauer-Spencer Thm, Bollobas-Eldridge Conj), graphic lists
5 1/28Fr: Aigner-Triesch for bigraphic lists, potentially k-edge-connected lists, vertex ptn for maximum degree
6 1/31Mo: vertex partition for minimum degree (Stiebitz), graph
reconstruction through Counting Theorem
7 2/02We: reconstruction of trees and almost all graphs,
edge-reconstruction
8 2/04Fr: isometric embedding & metric representation
9 2/07Mo: product dimension
Chapter 7: Connection and Cycles
10 2/09We: Edmonds' Branching Theorem and applications
11 2/11Fr: Lucchesi-Younger Theorem
12 2/14Mo: k-linked graphs, forced subdivisions
13 2/16We: ear decomposition, contraction lemma, 3-connected graphs, Halin example
14 2/18Fr: minimally k-connected graphs (Mader etc.), sketch of
Gyori-Lovasz Theorem
15 2/21Mo: Nash-Williams Orientation Theorem
16 2/23We: toughness (9/4-tough non-Hamiltonian), k-closure, density theorems
17 2/25Fr: Bondy-Chvatal condition for t dominating verts,
Las Vergnas condition, Lu's Theorem strengthening Chvatal-Erdos (skipping hard
case)
18 2/28Mo: Oberly-Sumner Theorem, Ryjacek closure (sketch), Erdos-Gallai
extremal result on circumference
19 3/02We: Bondy's Lemma on long paths, Fan's Theorem, Ghoula-Houri's Theorem
20 3/04Fr: Meyniel's Theorem (Bondy-Thomassen proof), gossip problem
Chapter 8: Planar and non-planar graphs
21 3/07Mo: MacLane/Whitney planarity criteria, Schnyder labelings and grid
embeddings
22 3/09We: Schnyder labelings (proofs)
23 3/11Fr: graph dimension, lemmas for Lipton-Tarjan Separator Theorem
24 3/14Mo: Lipton-Tarjan Separator Theorem, applications to independent sets
and pebbling
25 3/16We: Thomassen 3-colorability of planar graphs with girth at least 5
26 3/18Fr: Grotzsch's Theorem, Wernicke by discharging, reducibility of
Birkhoff diamond, Tait's Theorem
27 3/28Mo: interval number and total interval number of planar graphs
28 3/30We: thickness and pagenumber
29 4/01Fr: crossing number and application
30 4/04Mo: t-linear crossing numbers, genus, Heawood's Formula
31 4/06We: voltage graphs
Chapter 9: Graph minors and related topics
32 4/08Fr: graph minors, testing minors, K4-minor-free
= 2-decomposable
33 4/11Mo: treewidth, cops-and-robber
34 4/13We: brambles, min/max for treewidth
35 4/15Fr: graph minor approach, well-quasi-ordering for trees (sketch)
36 4/18Mo: cycle covers and flows
37 4/20We: 8-flow theorem
38 4/22Fr: modular flows, 6-flow theorem
39 4/25Mo: snarks and faithful covers
Chapter 10: Algebraic graph theory
40 4/27We: eigenvalues (up to bipartite graphs)
41 4/29Fr: eigenvalues of regular graphs
42 5/02Mo: strongly regular graphs (Friendship Theorem), Laplacian eigvals
43 5/04Mo: chromatic polynomial, rank polynomial