Sylabus
Párování v obecných grafech.
Hamiltonovské kružnice, Oreho podmínka, Chvátalův uzávěr.
Plochy vyššího rodu, zobecněná Eulerova formule, Heawoodova formule.
Lemma o kontrahovatelné hraně, Tutteho věta o 3-souvislých grafech, Kuratowského věta.
Barevnost grafů, Brooksova věta, Vizingova věta.
Tutteho polynom: různé definice, význačné body, prostor cyklů a řezů grafu.
Obyčejné a exponenciální vytvořující funkce.
Burnsideovo lemma, Pólyova enumerace, příklady aplikací.
Věta o slunečnici, Erdös-Ko-Radoova věta, Turánova věta.
Perfektni grafy, Dilworthova věta.
Chordální grafy.
Anotace
Přehledová přednáška o klasických výsledcích v kombinatorice a teorii grafů. Předpokládají se znalosti v rozsahu
NDMI011 nebo NDMA001.