1 1/21 Wed: overview sample of topics in course

Topic 1: Trees and Distance

2 1/23 Fri Sec 1.1: spanning trees with many leaves (min degree 3,
general min degree)

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

4 1/28 Wed Sec 1.2:
Hoffman-Singleton graph, small graphs with fixed order/diameter/maxdegree

5 1/30 Fri Sec 1.2:
oriented diameter (construction, Chvatal-Thomassen bound, sketch of diameter 2),diameter vs. average distance,

6 2/02 Mon Sec 1.2:
diameter vulnerability, independence bounds on connected domination and average
distance

7 2/04 Wed Sec 1.3:
squashed cube dimension (examples, eigenvalue bound, Winkler's Theorem)

8 2/06 Fri Sec 1.3:
bandwidth: density bound (caterpillars), boundary bound (grids),
increase under edge addition,
mention of edge bandwidth (*B'(G) >B(G)*)

Topic 2: Matching and Independence

9 2/09 Mon Sec 2.1:
Hall's Theorem with lower bound on #matchings,
Birkhoff-von Neuman Theorem and rancher/farmer problem,
Ore's defect formula, Konig-Egervary Theorem

10 2/11 Wed Sec 2.1:
Tutte 1-factor Theorem via Berge-Tutte Formula, Lovasz/Zaks #matchings in
k-connected graphs, Plesnik 1-factor after deleting edges from k-regular

11 2/13 Fri Sec 2.1:
smallest matching number in k-regular graphs, factor-critical graphs,
Gallai-Edmonds Structure Theorem

12 2/16 Mon Sec 2.2:
augmenting paths, fast bipartite matching,
weighted matching

13 2/18 Wed Sec 2.2:
Edmonds' Blossom algorithm, on-line ski rental, on-line bipartite matching
(sketch of algorithms, no proofs of bounds)

14 2/20 Fri Sec 2.3:
Tutte's *f*-Factor Theorem (reduction to 1-factors, necessity and
sufficiency)

15 2/23 Mon Sec 2.3:
Parity Lemma, Erdos-Gallai conditions, Kundu's Theorem,
regular factors in regular graphs (Hanson-Loten-Toft)

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

17 2/27 Fri Sec 2.4:
independence ratio in cubic triangle-free graphs (state results),
domination number (Arnautov-Payan bound, Gallai edge bound for fixed domination
number, odd dominating sets

18 3/02 Mon Sec 2.4:
independent domination in claw-free graphs, kernels in digraphs,
domination in Kneser graphs.

19 3/04 Wed Sec 2.4-3.1:
covering numbers and total domination of Kneser graphs,
introduction of generalized coloring parameters (Ok,Sk,Dk,Ck)

Topic 3: Basic Coloring

20 3/06 Fri Sec 3.1:
k-greedy coloring, Matula generalization of Brooks, Lovasz max degree partition

21 3/09 Mon Sec 3.1:
acyclic and star coloring (bounds in terms of max degree, in-coloring)

22 3/11 Wed Sec 3.1:
acyclic and star coloring (Alon-McDiarmid-Reed probabilistic construction,
A-C-K-K-R inductive construction, upper bound via F-reductions)

23 3/13 Fri Sec 3.2:
Descartes girth 6 & large chromatic number, construction for large
chromatic number & girth

24 3/16 Mon Sec 3.2:
Color-critical: generalized Hajos construction, minimum excess degree
(Gallai)

25 3/18 Wed Sec 3.2:
broom-free graphs weakly chi-bounded, (skipped Dirac K_4-subdivision), Hajos
and Hadwiger conjectures, min degree for F-subdivision

26 3/20 Fri Sec 3.3:
Anderson-Goldberg (Vizing-Gupta) Theorem, (skipped overfull/1-factorization
conjectures), Chvatal-McDiarmid Theorem

27 3/30 Mon Sec 3.3:
Vizing Adjacency Lemma, Erdos-Faber-Lovasz reduction, Chang-Lawler coloring of
linear hypergraphs

Topic 4: Refined Coloring Models & Perfection

28 4/1 Wed Sec 3.3:
Summary of parity edge-coloring and interval edge-coloring (proof of elementary
results, statement of others), skipped proper weighting

29 4/3 Fri Sec 3.4:
List coloring (very brief review of degree-choosability through list version of
Brooks), bipartite choosability vs. 2-coloring hypergraphs, Alon's
lower bound by average degree.

30 4/6 Mon Sec 3.4:
List coloring conjecture, Galvin's List Color Theorem, mentioned
Borodin-Kostochka-Woodall list version of Shannon, f-choosability and
3-choosability of planar bipartite graphs

31 4/8 Wed Sec 3.4: 3-choosability of squares of cycles, Alon-Tarsi Theorem

32 4/10 Fri Sec 3.4-3.5:
(1,2)-choosability of even trees, intro to circular coloring

33 4/13 Mon Sec 3.5:
properties of circular and (k,d)-colorings, condition for chi_c=chi,
Goddyn-Tarsi-Zhang generalization of Minty to circular coloring

34 4/15 Wed Sec 3.5-4.1:
upper bounds on chi_c by Steffen-Zhu, Zhu (generalizing Tuza),
brief intro to classical examples of perfect graphs

35 4/17 Fri Sec 4.1:
The Perfect Graph Theorem, comparability, chordal, perfectly orderable graphs

Topic 5: Extremal Problems

36 4/20 Mon Sec 5.1: Turan's Theorem, counting triangles (through
Moon-Moser), further comments on *k_p(G)*, Lovasz-Simonovits Theorem

37 4/22 Wed Sec 5.1: Zarankiewicz Problem and related topics, Erdos-Simonovits
from Erdos-Stone

38 4/24 Fri Sec 5.1: Erdos-Stone by Regularity Lemma and Embedding Lemma

39 4/27 Mon Sec 5.1: Proof of Regularity Lemma

40 4/29 Wed Sec 5.2: application of Regularity to linear Ramsey number for
bounded-degree graphs, Ramsey number for paths,
skipped induced Turan problems and anti-Ramsey numbers

41 5/01 Fri Sec 5.3:
decomposition problems (into complete graphs, forests (mention arboricity),
trees, linear forests)

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

43 5/06 Wed Sec 5.4: interval number, total interval number, visibility number