Barevnost grafů a kombinatorických struktur

Rozvržení: středa 15:40 v S10.

Obsah přednášek a poznámky
  1. Algoritmická složitost barvení grafů na plochách -> hustota kritických grafů.
  2. Brooksova věta a Gallaiovy stromy.
  3. Kritické grafy -- hustota, kritické grafy na plochách.
  4. Hustota 4-kritických grafu, důkaz Grötzschovy věty z hustoty 4-kritických grafů, další důsledky.
  5. Metoda přerozdělování náboje. Důkaz Grötzschovy věty přerozdělováním náboje.
  6. Barevnost a nikdenenulové toky, barevnost kvadrangulací, chromatický polynom.
  7. Věta o 4 barvách -- redukce, přerozdělování náboje.
  8. Barevnost a homomorfismy. Zlomková barevnost. Zlomková barevnost Mycielského grafů.
  9. Cirkulární barevnost. Orientace grafu a cirkulární barevnost. Cirkulární barevnost speciálních grafů.
  10. Aplikace pravděpodobnostní metody v barvení.
  11. Metoda entropy compression.