Koná se úterý 15:40–17:10 v S11.

1. 3.10.: List version of Brooks' theorem and Gallai trees.
2. 10.10., 17.10.: Critical graphs and algorithmic complexity of coloring graphs on surfaces. Density of critical graphs.
3. 23.10. (replacing the 24.10. lesson): Potential method: Density of 4-critical graphs and Grötzsch theorem.
4. 31.10.: Finished the potential method proof. A simple example for the discharging metod.
5. 7.11.: Discharging method: How to find a proof?
6. 14.11.: Grötzsch theorem using discharging.
7. 21.11.: Coloring and nowhere-zero flows.
8. 28.11., 5.12.: The proof of the Four Color Theorem.
9. 12.12.: List coloring in planar graphs.
10. 19.12.: Variants of graph coloring. Acyclic and star coloring. Defective and clustered coloring. Circular coloring, fractional coloring, homomorphisms.
11. 9.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.

Other materials:

• Presentation and notes from the presentation for the critical graphs and coloring graphs on surfaces.
• Grötzch theorem by discharging: Assignment description, the worksheet, the tex file for the worksheet.