• Home
  • My CV
  • Publications
  • Teaching/Výuka
  • My hobbies
  • Contact
  • Obecné informace
  • Témata bakalářských a diplomových prací
  • Diskrétní matematika
  • Kombinatorika a grafy II
  • Kombinatorika a grafy II (cvičení)
  • Kombinatorika a grafy III
  • Úvod do extremální teorie grafů
  • Lineární algebra I
  • Lineární algebra II
  • Teorie grafových minorů
  • Barevnost grafů a kombinatorických struktur
  • Praktikum řešení programátorských úloh
Barevnost grafů a kombinatorických struktur

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

Lecture notes
  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.