Barevnost grafů a kombinatorických struktur
Čtvrtek 14:00 v S5.
Obsah přednášek a poznámky
- 3.10.: Vybíravost.
- 10.10.: Brooksova věta a Gallaiovy stromy.
- 17.10.: Algoritmická složitost barvení grafů na plochách -> hustota kritických grafů.
- 24.10.: Kritické grafy -- hustota, kritické grafy na plochách.
- 31.10.: Hustota 4-kritických grafu, důkaz Grötzschovy věty z hustoty 4-kritických grafů, další důsledky.
- 20.11.: Metoda přerozdělování náboje. Důkaz Grötzschovy věty přerozdělováním náboje.
- 21.11.: Věta o 4 barvách -- redukce, přerozdělování náboje.
- 5.12.: Aplikace pravděpodobnostní metody v barvení.
- 11.12.: Metoda entropy compression.
- 9.1.: Barevnost a nikdenenulové toky, barevnost kvadrangulací.