Lec 1 1/21 Wed: overview sample of topics in course
Lec 2 1/23 Fri Sec 1.1: spanning trees with many leaves, optimal alphabetic trees (dynamic programming)
Lec 3 1/26 Mon Sec 1.1: Hu-Tucker alphabetic tree algorithm, Moore graphs, small graphs with fixed order and diameter and maximum degree
Lec 4 1/28 Wed Sec 1.2: oriented diameter, diameter vs. average distance
Lec 5 1/30 Fri Sec 1.2: average distance vs. independence number, squashed
cube embeddings
Lec 6 2/2 Mon Sec 1.3: squashed cube dimension (eigenvalue lower bound,
n(G)-1 upper bound)
Lec 7 2/4 Wed Sec 1.3: bandwidth (bounds, caterpillars, grids)
Lec 8 2/6 Fri Sec 1.3: bandwidth (edge addition, Sperner Lemma/simplex,
brief mention of edge bandwidth)
Lec 9 2/9 Mon Sec 2.1: Hall's Theorem (with lower bound on #matchings),
Birkhoff-von Neuman Theorem and rancher/farmer problem, Ore's min-max formula,
Konig-Egervary Theorem
Lec 10 2/11 Wed Sec 2.1: Tutte 1-factor Theorem, Berge-Tutte Formula, Berge
generalization of Petersen's Theorem
Lec 11 2/13 Fri Sec 2.1: Gallai-Edmonds Structure Theorem, counting 1-factors
in k-connected graphs, (skipped Van der Waerden)
Lec 12 2/16 Mon Sec 2.2: fast bipartite matching, Edmonds' Blossom algorithm
Lec 13 2/18 Wed Sec 2.2: weighted matching, deterministic on-line problems (ski
rental, matching)
Lec 14 2/20 Fri Sec 2.2: on-line matching (randomized algorithms)
Lec 15 2/23 Mon Sec 2.3: f-factor reduction, Tutte f-Factor Theorem
Lec 16 2/25 Wed Sec 2.3: Erdos-Gallai conditions, statement of other factor
results
Lec 17 2/27 Fri Sec 2.4: independent sets (characterization of maximum stable
sets, Caro-Wei Theorem, critical edges, triangle-free graphs)
Lec 18 3/01 Mon Sec 2.4: independent domination in claw-free graphs, etc.
Lec 19 3/03 Wed Sec 2.4: kernels in digraphs, odd dominating sets
Lec 20 3/05 Fri Sec 3.1: vertex coloring, Minty's theorem
Lec 21 3/12 Fri Sec 3.1: generalized coloring, Brooks generalization
Lec 22 3/15 Mon Sec 3.2: Lovasz max degree coloring, construction with
chromatic number & girth
Lec 23 3/17 Wed Sec 3.2: broom-free graphs weakly chi-bounded,
Hajos and Hadwiger, min degree for F-subdivision
Lec 24 3/18 Thu Sec 3.3: overfull/1-fac conjectures, Vizing's Theorem
Lec 25 3/19 Fri Sec 3.3-4: edge-coloring of linear hypergraphs, list coloring
Lec 26 3/29 Mon Sec 3.4: degree-choosable, Gallai/Brooks list generalization
Lec 27 3/31 Wed Sec 3.4: lower bound by average degree (Alon), list coloring
conjecture, Galvin's Theorem
Lec 28 4/01 Thu Sec 3.4: 3-choosability of planar bipartite, Alon-Tarsi
Lec 29 4/02 Fri Sec 3.4-5: precoloring extension, circular coloring
Lec 30 4/05 Mon Sec 3.5: (k,d)-coloring, chi_c=chi
Lec 31 4/07 Wed Sec 3.5: chi_c small, graph homomorphisms
Lec 32 4/09 Fri Sec 4.1: perfect graph examples, the Perfect Graph Theorem
Lec 33 4/12 Mon Sec 4.1: perfectly orderable graphs, Meyniel graphs
Lec 34 4/14 Wed Sec 4.2: comments on partitionable graphs and Strong Perfect
Graph Theorem
Lec 35 4/16 Fri Sec 4.3: chordal graphs (characterizations, properties, and
recognition)
Lec 36 4/19 Mon Sec 4.3: strongly chordal graphs (characterizations)
Lec 37 4/21 Wed Sec 4.3: comments on bichordal, interval, threshold, tolerance,
and parity graphs
Lec 38 4/23 Fri Sec 5.2: graph Ramsey theory (trees/cliques,
mK3, paths)
Lec 39 4/26 Mon Sec 5.2: linear Ramsey number for bounded-degree graphs
Lec 40 4/28 Wed Sec 5.2-3: anti-Ramsey number for cycles, greedy clique
decomposition
Lec 41 4/30 Fri Sec 5.3: arboricity, decomposition into trees
Lec 42 5/03 Mon Sec 5.3-4: Lovasz path/cycle decomposition, intersection
number, boxicity, interval number
Lec 43 5/05 Wed Sec 5.4: interval number, total interval number, visibility
number