Graph Theory II

Andrzej Ruciński

Date	Topic	Comments
1 III	Lecture 1 (doubled, instead of exercises): Matchings in general graphs	*Problem Set 1*
8 III	Lecture 2: Path covers (of directed graphs)	*Problem Set 2*
15 III	Lecture 3: Vertex Colorings	*Problem Set 3*
22 III	Lecture 4: Coloring planar graphs	*Problem Set 4* *Lectures 3 and 4*
29 III	Lecture 5: List colorings, edge colorings	*Problem Set 5* *Lecture 3,4, and 5* *Mirzhakhani paper (for in-class presentation -- a volunteer needed)*
4 IV	Lecture 6: Edge colorings (Vizing's Theorem)	*Problem Set 5* *Lecture 6* *Quite Easily Done (suggested reading)*
12 IV	Lecture 7: Coloring edges from lists	*Problem Set 6* *Lecture 7*
18 IV	Lecture 8: Perfect graphs: chordal graphs	*Problem Set 7* *Lecture 8*
25 IV	Lecture 9: Perfect graphs: weak conjecture	*Problem Set 7* *Lecture 9*
9 V	Lecture 10: Szemeredi's regularity lemma.	*Problem Set 8* *Lecture 10*
16 V	Lecture 11: Szemeredi's regularity lemma.	*Problem Set 8* *Lecture 10*
23 V	Lecture 12: The blow-up lemma.	*Problem Set 8* *Lecture 11*
30 V	Lecture 13: The Erdos-Stone Theorem via Blow-up Lemma.	*Problem Set 9* *Lecture 11/12*
6 VI	Exercises only: The Erdos-Stone Theorem via Blow-up Lemma.	*Problem Set 9* *Lecture 11/12*
21 VI	Lectute 14 (by Dr. Joanna Polcyn): Ramsey numbers for sparse graphs via Blow-up Lemma.	*Problem Set 10* *Lecture 13*
27 VI	(Optional) oral exam: 11:30am - 2pm, room B3-23