Topic 1: Trees and Distance

Lec1 1/19 Wed Sec 1.1: spanning trees with many leaves (min degree 3,
general min degree)

Lec2 1/21 Fri Sec 1.1:
Huffman coding, Shannon bound, optimal alphabetic trees (dynamic programming,
Hu-Tucker algorithm), intro to eccentricity/radius/diameter
(Harary-Norman)

Lec3 1/24 Mon Sec 1.2:
Moore bound, Hoffman-Singleton graph, small graphs with fixed
order/diameter/maxdegree

Lec4 1/26 Wed Sec 1.2:
oriented diameter (construction, Chvatal-Thomassen bound,
brief sketch of improvement for diameter 2)

Lec5 1/28 Fri Sec 1.2:
diameter vs. average distance, diameter vulnerability, independence bounds on
connected domination and average distance

Lec6 1/31 Mon Sec 1.3:
squashed-cube dimension (examples, eigenvalue bound, Winkler's Theorem)

x 2/02 Wed: Snow Day

Lec7 2/04 Fri Sec 1.3:
bandwidth: density bound (caterpillars), boundary bound (grids),
increase under edge addition, Sperner's Lemma (triangular grid),
mention of edge bandwidth (*B'(G) >B(G)*)

Topic 2: Matching and Independence

Lec8 2/07 Mon Sec 2.1:
Hall's Theorem with lower bound on #matchings,
rancher/farmer problem (Marcus-Ree Theorem), review of classical applications
(Marriage Theorem, Birkhoff-von Neuman Theorem,
Ore's Defect Formula, Konig-Egervary Theorem),
Tutte 1-factor Theorem via Berge-Tutte Formula

Lec9 2/09 Wed Sec 2.1:
Gallai-Edmonds Structure Theorem, state Plesnik's Theorem (review),
Lovasz/Zaks #matchings in k-connected graphs,
smallest matching number in k-regular graphs

Lec10 2/11 Fri Sec 2.2:
augmenting paths, fast bipartite matching,
Edmonds' Blossom algorithm, intro to weighted matching

Lec11 2/14 Mon Sec 2.2:
weighted matching, on-line ski rental, on-line bipartite matching
(mostly overview)

Lec12 2/16 Wed Sec 2.3:
Tutte's *f*-Factor Theorem (reduction to 1-factors, necessity and
sufficiency)

Lec13 2/18 Fri Sec 2.3:
Parity Lemma, Erdos-Gallai conditions,
regular factors in regular graphs (Hanson-Loten-Toft),
skipped toughness, briefly mentioned *g,f*-factor problem and
complexity of testing

Lec14 2/21 Mon Sec 2.4:
maximum stable sets (Berge characterization), greedy algorithms,
Caro-Wei Theorem, critical edges, Bondy bound on vertex cover number.

Lec15 2/23 Wed Sec 2.4:
independence ratio in cubic triangle-free graphs (state results),
domination number (Arnautov-Payan bound, Gallai edge bound for fixed domination
number

Lec16 2/25 Fri Sec 2.4:
odd dominating sets, independent domination in claw-free graphs,
kernels in digraphs, introduction to generalized coloring (families
**O**k, **S**k, **D**k, **C**k)

Topic 3: Coloring

Lec17 2/28 Mon Sec 3.1:
k-greedy coloring, Matula generalization of Brooks, Lovász partition
into classes with bounded maximum degree

Lec18 3/02 Wed Sec 3.1:
acyclic coloring (upper bound algorithm for maxdegree 3, general maxdegree,
Alon-McDiarmid-Reed probabilistic lower bound), star coloring (equivalence with
in-coloring)

Lec19 3/04 Fri Sec 3.1:
star coloring (quadratic maxdegree upper bound, mention upper bound via acyclic
coloring, acyclic and star coloring for planar graphs, A-C-K-K-R inductive
construction), nonrepetitive coloring (sketch bound of 4 for trees),
start injective coloring (degree upper bound)

Lec20 3/07 Mon Sec 3.2:
(finish injective coloring for Mad(G)≤36/13), Descartes girth 6 & large
chromatic number, construction for large chromatic number & girth

Lec21 3/09 Wed Sec 3.2:
Color-critical: generalized Hajos construction, minimum excess degree
(Dirac by statement, prove Gallai's bound)

Lec22 3/11 Fri Sec 3.2:
broom-free graphs weakly chi-bounded, Dirac K_4-subdivision, Hajos
and Hadwiger conjectures, min degree for F-subdivision

Lec23 3/14 Mon Sec 3.3:
review of elementary coloring results (Konig, Vizing-Gupta,
Anderson-Goldberg), (skipped Vizing Adjacency Lemma),
Erdos-Faber-Lovasz reduction, Chang-Lawler coloring of linear hypergraphs

Topic 4: Refined Coloring Models & Perfection

Lec24 3/16 Wed Sec 3.3:
parity edge-coloring

Lec25 3/18 Fri Sec 3.3:
interval edge-coloring (proof of elementary
results, statement of others), skipped proper weighting

Lec26 3/28 Mon Sec 3.4:
List coloring (bipartite choosability vs. 2-coloring hypergraphs, Alon's
lower bound from average degree).

Lec27 3/30 Wed Sec 3.4:
List coloring conjecture, *f*-choosability and kernels, Galvin's List
Color Theorem, Borodin-Kostochka-Woodall list version of Shannon

Lec28 4/01 Fri Sec 3.4:
3-choosability of planar bipartite graphs,
Alon-Tarsi Theorem (3-choosability of squares of cycles),

Lec29 4/04 Mon Sec 3.4:
Combinatorial Nullstellensatz and applications
(skipped (1,2)-choosability of even trees)

Lec30 4/06 Wed Sec 3.5:
intro to circular coloring, properties of circular and (k,d)-colorings,
condition for *χ _{c}=χ*

Lec31 4/08 Fri Sec 3.5: Goddyn-Tarsi-Zhang generalization of Minty to circular coloring upper bounds on

Lec32 4/11 Mon Sec 4.1: classical examples of perfect graphs, comparability, chordal, The Perfect Graph Theorem

Lec33 4/13 Wed Sec 4.1: perfectly orderable graphs, star-cutset lemma, comments on Meyniel graphs and weakly chordal graphs

Lec34 4/15 Fri Sec 4.2-3: comments on partitionable graphs and Strong Perfect Graph Theorem, chordal graphs (intersection representation)

Lec35 4/18 Mon Sec 4.3: comments on split, strongly chordal/bichordal graphs, characterizations of interval graphs (skipped unit interval), comments on threshold and parity graphs

Topic 5: Extremal Problems

Lec36 4/20 Wed Sec 5.1: Turan's Theorem, counting triangles (through
Moon-Moser), further comments on *k _{p}(G)*, state
Lovasz-Simonovits Theorem

Lec37 4/22 Fri Sec 5.1: saturation numbers, Erdos-Simonovits from Erdos-Stone, Erdos-Stone by Nikiforov

Lec38 4/25 Mon Sec 5.1: extremal problems for hypergraphs, covering numbers, Chvatal-McDiarmid theorem.

Lec39 4/27 Wed Sec 5.2: graph Ramsey numbers (tree/clique,

Lec40 4/29 Fri Sec 5.2: multicolor bipartite Ramsey for

Lec41 5/02 Mon Sec 5.3: decomposition problems (into complete graphs, forests (mention arboricity), trees, linear forests, fractional arboricity)

Lec42 5/04 Wed Sec 5.3-4: Lovasz path/cycle decomposition, intersection number, boxicity

Lec43 5/05 Thu Sec 5.4: boxicity, interval number, brief mention of total interval number, skipped visibility number !-->