Barevnost grafů a kombinatorických struktur - NDMI060

• Anglický název: Coloring of Graphs and Other Combinatorial Structures
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Třída: DS, diskrétní modely a algoritmy; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: T_KAM (26.04.2003)

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.

Podmínky zakončení předmětu

čeština

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2019)

Ústní zkouška.

angličtina

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (07.06.2019)

Oral exam.

Literatura

Poslední úprava: 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.

Požadavky ke zkoušce

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: prof. Mgr. Zdeněk Dvořák, Ph.D. (06.10.2017)

Oral exam consisting of 2-3 questions on subjects covered by the lectures.

Sylabus

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: 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.