Koná se úterý 14:00 – 15:30 v S10.

1. 5.10: List version of Brooks' theorem and Gallai trees.
2. 12.10: Critical graphs and algorithmic complexity of coloring graphs on surfaces. Presentation, notes from the presentation.
3. 26.10.: Density of critical graphs.
4. 2.11. and 9.11.: Potential method: Density of 4-critical graphs and Grötzsch theorem.
5. 16.11.: Discharging.
6. 23.11.: Grötzsch theorem using discharging: Assignment description, the worksheet, the tex file for the worksheet. Lecture notes (with a slightly different proot).
7. 30.11., 7.12.: The proof of the Four Color Theorem.
8. 14.12.: Coloring and nowhere-zero flows.
9. 21.12.: Variants of graph coloring (acyclic and star coloring, defective and clustered coloring).
10. 4.1.: Coloring of triangle-free graphs and the Rosenfeld counting method.

Lecture notes from the past years:

• Cirkulární barevnost. Orientace grafu a cirkulární barevnost.
• Barevnost a homomorfismy. Zlomková barevnost. Zlomková barevnost Mycielského grafů.
• Vybíravost.
• Entropy compression method.
• Applications of the probabilistic method in graph coloring.