SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Graph minor theory - NDMI085
Title: Teorie grafových minorů
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023 to 2023
Semester: summer
E-Credits: 6
Hours per week, examination: summer s.:2/2, C+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: Informatika Mgr. - volitelný
Classification: Informatics > Discrete Mathematics
Annotation -
The lecture covers the graph minor theory based on the results of Robertson and Seymour, with the emphasis on the new trends in this area. The knowledge of the results covered by NDMI059 or NDMI073 is assumed.
Last update: T_KAM (04.05.2011)
Course completion requirements -

Passing grade for tutorials (zápočet) is obtained on the basis of active participation, especially discussions of the solutions of the homework problems assigned during the lectures and presentations of studied papers; in exceptional cases, individual consultations can be used instead. The nature of these requirements precludes retakes. Passing grade for tutorials is required before taking the exam, this can be relaxed at the discretion of the lecturer in exceptional cases (early exam dates).

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

N. Robertson, P. Seymour, Graph Minors I-XXIII.

Ken-ichi Kawarabayashi, Paul Wollan: A shorter proof of the graph minor algorithm: the unique linkage theorem. STOC 2011, 687-694.

K. Kawarabayashi, S. Norin, R. Thomas, P. Wollan: K_6 minors in 6-connected graphs of bounded tree-width, manuscript.

N. Robertson, P. Seymour, R. Thomas: Hadwiger's conjecture for K_6-free graphs, Combinatorica 13 (1993), no. 3, 279-361.

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

Oral exam consisting of 2-3 questions regarding general overview of topics covered by the lectures and a more detailed discussion of one of the topics, assigned in advance.

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

Properties of graphs on surfaces, tree decompositions and the structure of the graphs without a forbidden minor, well-quasiordering by the minor relation, testing of existence of disjoint paths and of minors, the structure of t-connected graphs without K_t and the connection to Hadwiger conjecture.

Last update: T_KAM (04.05.2011)
Charles University | Information system of Charles University |