V této přednášce vyložíme teorii grafových minorů založenou na výsledcích Robertsona a Seymoura, se
zaměřením na nové trendy v této oblasti. Předpokládají se znalosti v rozsahu přednášky NDMI059 nebo
NDMI073.
Poslední úprava: 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.
Literatura -
Poslední úprava: 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.
Poslední úprava: 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.
Sylabus -
Poslední úprava: T_KAM (04.05.2011)
Vlastnosti grafů na plochách, stromové rozklady a struktura grafů bez zakázaného minoru, minorová relace definuje dobré uspořádání, testování existence disjunktních cest a minorů, struktura t-souvislých grafů bez K_t a souvislost s Hadwigerovou hypotézou.
Poslední úprava: 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.
