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