SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Coloring of Graphs and Other Combinatorial Structures - NDMI060
Title: Barevnost grafů a kombinatorických struktur
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023 to 2023
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Teaching methods: full-time
Guarantor: prof. Mgr. Zdeněk Dvořák, Ph.D.
Class: DS, diskrétní modely a algoritmy
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics
Annotation -
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)
Course completion requirements -

Oral exam.

Last update: Pangrác Ondřej, RNDr., Ph.D. (07.06.2019)
Literature - Czech

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.

Last update: T_KAM (26.04.2003)
Requirements to the exam -

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

Last update: Dvořák Zdeněk, prof. Mgr., Ph.D. (06.10.2017)
Syllabus -

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: Dvořák Zdeněk, prof. Mgr., Ph.D. (21.09.2016)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html