Lecture: Thursday 15:40–17:10 in S10.

1. 2.10.: What do we already know about graph coloring (4-color theorem, Brooks and Vizing's theorems, Heawood's formula, triangle-free graphs with large chromatic number, …). Critical graphs and algorithmic complexity of coloring graphs on surfaces.
2. 9.10.: Introduction to list coloring. List version of Brooks' theorem and Gallai trees.
3. 16.10.: Density of critical graphs. Constructions of infinitely many 5-critical graphs and infinitely many 4-critical triangle-free graphs on surfaces of non-zero genus.
4. 23.10.: Coloring and nowhere-zero flows.
5. 30.10: Discharging method: How to find a proof?
6. 6.11.: Grötzsch theorem using discharging.
7. 13.11.: The proof of the Four Color Theorem.
8. 20.11.: List coloring in planar graphs.
9. 27.11.: Potential method: Density of 4-critical graphs and Grötzsch theorem.
10. 4. a 11.12.: Variants of graph coloring. Acyclic and star coloring. Defective and clustered coloring. Circular coloring, fractional coloring, homomorphisms.
11. 18.12.: Coloring of triangle-free graphs and the Rosenfeld counting method.
12. 8.1.: Probabilistic method in graph coloring.

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.