Barevnost grafů a kombinatorických struktur

Rozvržení: ...

Obsah přednášek a poznámky
  1. Algoritmicka slozitost barveni grafu na plochach -> hustota kritickych grafu -> seznamova barevnost.
  2. Brooksova veta a Gallaiovy stromy. Kriticke grafy -- hustota, kriticke grafy na plochach.
  3. Hustota 4-kritickych grafu.
  4. Dukaz Grotzschovy vety z hustoty 4-kritickych grafu, dalsi dusledky.
  5. Metoda prerozdelovani naboje. Dukaz Grotzschovy vety prerozdelovanim naboje.
  6. Veta o 4 barvach -- redukce, prerozdelovani naboje.
  7. Zlomkova barevnost. Zlomkova barevnost Mycielskeho grafu.
  8. Cirkularni barevnost. Orientace grafu a cirkularni barevnost. Cirkularni barevnost specialnich grafu.
  9. Barevnost a nikdenenulove toky.
  10. Aplikace pravdepodobnostni metody v barveni.
  11. Entropy compression.
Další materiály a zdroje

Vybiravost a prumerny stupen (kapitola 2.2).