Coloring of graphs and their classes (in particular, graphs on surfaces). Proof techniques used to bound the chromatic number of graphs (the probabilistic method, an algebraic approach, discharging).Tutte's polynomial. Generalizations and special types of coloring:
diagonal and cyclic coloring, list-coloring, channel assignment, L(2,1)-coloring, T-coloring, etc. Coloring of other combinatorial structures.
Last update: T_KAM (26.04.2003)
Barevnost grafů a jejich speciálních tříd (zejména grafů na plochách). Důkazové techniky používané při odhadech barevnosti grafů (pravděpodobnostní metoda, algebraické metody, metoda přerozdělování náboje). Tuttův polynom. Zobecnění a speciální typy barvení grafů: diagonální, cyklické, vybíravost, channel assignment, L(2,1)-barvení, T-barvení apod. Barevnost jiných kombinatorických struktur.
Course completion requirements -
Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2019)
Oral exam.
Last update: RNDr. Ondřej Pangrác, Ph.D. (07.06.2019)
Ústní zkouška.
Literature - Czech
Last update: T_KAM (26.04.2003)
1. Bollobas, B.: Modern Graph Theory. Springer-Verlag, New York (1998).
2. Tommy R. Jensen and Bjarne Toft. Graph Coloring Problems. Discrete Mathematics and Optimization. Wiley and Sons, New York, 1995.
3. R. Diestel, "Graph Theory," Graduate Texts in Math., Vol. 173, Springer-Verlag, New York, NY, 1997.
Requirements to the exam -
Last update: prof. Mgr. Zdeněk Dvořák, Ph.D. (06.10.2017)
Oral exam consisting of 2-3 questions on subjects covered by the lectures.
Last update: prof. Mgr. Zdeněk Dvořák, Ph.D. (06.10.2017)
Zkouška proběhne ústní formou, v rozsahu 2-3 otázek pokrytých látkou probranou na přednáškách.
Syllabus -
Last update: prof. Mgr. Zdeněk Dvořák, Ph.D. (21.09.2016)
Coloring of graphs and their classes (in particular, graphs on surfaces). Proof techniques used to bound the chromatic number of graphs (the probabilistic method, an algebraic approach, discharging).Tutte's polynomial. Generalizations and special types of coloring: diagonal and cyclic coloring, list-coloring, channel assignment, L(2,1)-coloring, T-coloring, etc. Coloring of other combinatorial structures.
Last update: prof. Mgr. Zdeněk Dvořák, Ph.D. (21.09.2016)
Barevnost grafů a jejich speciálních tříd (zejména grafů na plochách). Důkazové techniky používané při odhadech barevnosti grafů (pravděpodobnostní metoda, algebraické metody, metoda přerozdělování náboje). Tuttův polynom. Zobecnění a speciální typy barvení grafů: diagonální, cyklické, vybíravost, channel assignment, L(2,1)-barvení, T-barvení apod. Barevnost jiných kombinatorických struktur.
