Charles Explorer logo
🇬🇧

Combinatorics and Graph Theory 2

Class at Faculty of Mathematics and Physics |
NDMI012

Syllabus

Matchings in general graphs.

Hamiltonian cycles, Ore condition, Chvátal closure.

Surfaces of higher genus, generalized Euler's formula, Heawood's formula.

Lemma on the contractible edge, Tutte's theorem on 3-connected graphs, Kuratowski's theorem.

Graph coloring, Brooks' theorem, Vizing's theorem.

Tutte polynomial: equivalent definitions, important points, cycle space, and cut space of a graph.

Ordinary and Exponential Generating Functions.

Burnside's lemma, Polya's enumeration, examples of applications.

Sunflower theorem, Erdös-Ko-Rado Theorem, Turan's Theorem

Perfect graphs, Dilworth's theorem.

Chordal graphs.

Annotation

The lecture extends NDMI011. An overview lecture on classical results in combinatorics and graph theory.