Kombinatorika a grafy 2

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.