Barevnost grafů a kombinatorických struktur
Koná se úterý 14:00 – 15:30 v S10.
Lecture notes
- 5.10: List version of Brooks' theorem and Gallai trees.
- 12.10: Critical graphs and algorithmic complexity of coloring graphs on surfaces. Presentation, notes from the presentation.
- 26.10.: Density of critical graphs.
- 2.11. and 9.11.: Potential method: Density of 4-critical graphs and Grötzsch theorem.
- 16.11.: Discharging.
- 23.11.: Grötzsch theorem using discharging: Assignment description, the worksheet, the tex file for the worksheet. Lecture notes (with a slightly different proot).
- 30.11., 7.12.: The proof of the Four Color Theorem.
- 14.12.: Coloring and nowhere-zero flows.
- 21.12.: Variants of graph coloring (acyclic and star coloring, defective and clustered coloring).
- 4.1.: Coloring of triangle-free graphs and the Rosenfeld counting method.