Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Graph minor theory - NDMI085

Title:	Teorie grafových minorů
Guaranteed by:	Department of Applied Mathematics (32-KAM)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2016 to 2016
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:	not 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

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: T_KAM (04.05.2011)

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.

Literature -

Last update: T_KAM (04.05.2011)

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.

Syllabus -

Last update: T_KAM (04.05.2011)

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.