The lecture will take place on Thursday at 8:00 in the lecture room S1 and will be followed by the recitation in the same room. Both the lecture and the recitation will be taught by myself.
The lecture will cover topics of various areas of graph theory and combinatorics in more detail than in the obligatory courses, in particular, topics from structural graph theory (graph minors, graph colorings and Regularity Lemma) and extremal combinatorics. The lecture was created by moving the most difficult topics from the lecture DMI012 Combinatorics and Graph Theory II and thus it is not intended for students who passed this lecture in 2006/07 or 2007/08; the content will hugely overlap.
The exam is oral. You will be given two problems; one of the problems will be to state and prove a theorem from the lecture. About one and half hours should be sufficient to solve the problems.
Use the university web system (https://is.cuni.cz/studium/login.php) for signing up for the exams. The exam dates are Jan 19, Jan 23, Jan 26, Jan 30, Feb 2, Feb 6 and Feb 20. For each day, there are several slots for which you can sign up; the first slot is at 9:00, the next one at 10:00, etc. Sign up for the earliest available slot. New slots will be open when the current ones get full. You can sign out until two days before the exam and sign up until one day before.
The exam slots are supposed to evenly distribute the students during the day for the exams. If you come earlier, feel free to enter the lecture room - you will be given the problems and you can start solving it immediately.
| 16/10 | graph minors, graph classes with no Kn-minor, 2-trees, Hadwiger's conjecture |
| 23/10 | chordal graphs, k-trees, tree decompositions, Courcelle's theorem (beginning) |
| 30/10 | Courcelle's theorem, structural theorems for minor-closed classes of graphs |
| 6/11 | Mader's theorem on a subdivision of a complete graph, linked graphs |
| 13/11 | Hales-Jewett, Gallai-Witt and van der Waerden theorems, Turan theorem |
| 20/11 | Szemeredi Regularity Lemma, Removal Lemma for triangles |
| 27/11 | Erdos-Stone theorem |
| 4/12 | list colorings, list 2-colorable graphs, Thomassen's theorem on planar graphs |
| 11/12 | computational complexity of list colorings |
| 18/12 | Galvin's theorem, explicit construction of high-chromatic graphs with no triangles |