The lecture will be given on Monday from 10:40 to 12:10 in the lecture room S1 in the building in Mala Strana. The lecture will be taught by myself and professor Riste Skrekovski from University of Ljubljana; both of us will be lecturing in English. The lecture will cover topics of various areas of graph colorings, in particular, we focus on various relaxations of graph colorings, algebraic methods, the discharging method and related topics such as nowhere-zero flows in graphs.
The exam is oral. You will be asked to prove a theorem presented at the lecture or a slight modification of its statement.
Use the university web system (https://is.cuni.cz/studium/login.php) for signing up for the exams. The exam dates are 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 exam problem and you can start solving them immediately. Note that both the lecturers can be examining on each of the days.
| 6/10 | DK | Brooks' theorem for list colorings, Gallai trees |
| 13/10 | R© | critical graphs, critical graphs on surfaces |
| 20/10 | DK | list chromatic number of dense graphs |
| 27/10 | DK | circular colorings, colorings and orientations of graphs |
| 3/11 | DK | circular edge-colorings of cubic bridgeless graphs |
| 10/11 | R© | Alon-Tarsi theorem - the proof |
| 17/11 | no lecture | |
| 24/11 | DK | Alon-Tarsi theorem - applications (planar bipartite graphs, cycle+triangles problem) |
| 1/12 | R© | overview of the discharging method |
| 8/12 | R© | example of use of the discharging method - reducible configurations |
| 15/12 | BL | example of use of the discharging method - discharging phase |
| 12/1 | R© | Grotschz theorem |
| 19/1 | R© | Grotschz theorem (end of the proof) |