1 1/14Mo: introduction (overview of topics)
Chapter 6: Elementary Structural Concepts
2 1/16We: Matrix Tree background, Matrix Arborescence Theorem,
counting Eulerian circuits
3 1/18Fr: graceful labelings (hypercubes), T-decomposition (girth vs diameter)
4 1/23We: graph packing (Sauer-Spencer Thms, Bollobas-Eldridge Conj)
5 1/25Fr: Hajnal-Szemeredi Theorem (new proof)
6 1/28Mo: graphic lists (2-switch, Aigner-Triesch method),
7 1/30We: potentially k-edge-connected lists, vertex ptns under maximum
or minimum degree constraints
8 2/01Fr: graph reconstruction (counting arguments, disconnected graphs,
tree preliminaries)
9 2/04Mo: reconstruction (trees, almost all graphs), edge-reconstruction
10 2/06We: isometric embedding & metric representation
11 2/08Fr: product dimension
Chapter 7: Connection and Cycles
12 2/11Mo: Edmonds' Branching Theorem and applications, sketch of
Lucchesi-Younger Theorem
13 2/13We: k-linked graphs, forced subdivisions
14 2/15Fr: reminder of ear decomposition, contraction lemma & 3-connected
graphs (sketch of Tutte characterization), Halin example, minimally
k-connected graphs (Mader etc.)
15 2/18Mo: Gyori-Lovasz Theorem, proof for gossip theorem
16 2/20We: Nash-Williams Orientation Theorem
17 2/22Fr: toughness (9/4-tough non-Hamiltonian), k-closure, density
conditions (Bondy-Chvatal condition for t dominating verts,
Las Vergnas condition)
18 2/25Mo: Lu's Theorem strengthening Chvatal-Erdos (skipping hard case)
19 2/27We: Hamiltonian claw-free graphs (Matthews-Sumner Conjecture,
Ryjacek closure)
20 2/29Fr: circumference (Erdos-Gallai Thm, Bondy's Lemma on long paths,
Bermond's Theorem, Fan's Theorem), digraphs skipped (Ghoula-Houri, Meyniel)
Chapter 8: Planar and non-planar graphs
21 3/03Mo: MacLane/Whitney planarity criteria, Schnyder labeling & grid
embedding overview
22 3/05We: Schnyder labelings (proofs)
23 3/07Fr: Reducibility of Birkhoff diamond, discharging technique
(Wernicke, Borodin's light triangles)
Note: skipped Tait's and Grinberg's Theorems and Hamiltonicity in planar
graphs
24 3/10Mo: Grotzsch's Theorem, Thomassen 3-colorability of planar graphs
with girth at least 5
25 3/12We: Jaeger's Conjecture (circular coloring of planar graphs with
large girth)
26 3/14Fr: Lipton-Tarjan Separator Theorem, sketch of application to
independent sets (skipped pebbling)
27 3/24Mo: counting perfect matchings in planar bipartite graphs (Kasteleyn)
28 3/26We: interval number and total interval number of planar graphs
29 3/27Th: thickness and pagenumber
30 3/31Mo: crossing number and application
31 4/02We: t-linear crossing numbers, genus, Heawood's Formula
32 4/04Fr: voltage graphs
Chapter 9: Graph minors and related topics
33 4/07Mo: graph minors, testing minors, K4-minor-free
= 2-decomposable
34 4/09We: treewidth characterizations, cops-and-robber
35 4/11Fr: brambles, min/max for treewidth
36 4/14Mo: approach to graph minor theorem, well-quasi-ordering for trees
37 4/16We: cycle covers and flows
38 4/18Fr: 8-flow theorem
39 4/21Mo: modular flows, 6-flow theorem
Chapter 10: Algebraic aspects of graphs
40 4/23We: eigenvalues (basics, bipartite graphs, diameter)
41 4/25Fr: interlacing, bounds on largest eigenvalue, eigenvalues of
regular graphs
42 4/28Mo: eigenvalues and expanders, strongly regular graphs (Friendship Theorem)
43 4/30We: chromatic polynomial, with relation to rank and Tutte
polynomials