Vyuka - Teorie grafovych minoru

Obsah prednasky:

Popis struktury grafu bez zakazaneho minoru a teoreticke a algoritmicke aplikace tohoto popisu. Hlavni myslenky a metody dukazu (tangle, stromova sirka a zdi; vlastnosti grafu na plochach; linkovanost) a jejich dalsi vyuziti. Pripadne dle zajmu novejsi vysledky (struktura grafu se zakazanym podrozdelenim, strukturalni veta pro matroidy, ...).

Kdy a kde:

streda 14:00-17:10 S6

Odprednesena latka:

Datum	Obsah prednasky	Zdroje
19.2.	Opakovani, definice, hlavni myslenky a ingredience dukazu strukturalni vety.
26.2.	Stromova sirka a tangle.	Minory X; Priklady ke cviceni
5.3.	Velka stromova sirka vynucuje velkou zed.	Highly Connected Sets and the Excluded Grid Theorem
12.3.	Tangle a metrika na plochach.	Minory XI, XII; Priklady ke cviceni
26.3.	Plochy a linkovani.	Minory VI, VII a VIII
2.4.	2-linkage a jejich zobecneni (transakce).	Minory IX
???	Rozsirovani vnoreni.	Minory XIV a XV
???	Strukturalni veta.	Minory XVI, plan utoku.
???	Testovani existence minoru.	Minory XIII,XXI,XXII
???	Stromove rozklady a dobre usporadani.	Minory IV
???	Plochy a dobre usporadani.	???
???	Wagnerova hypoteza.	Minory X, XX

Doporucena literatura:

Kopie vsech zde uvedenych clanku mam k dispozici a mohu na pozadani zapujcit.

N. Robertson, P. Seymour: Graph Minors. I. - XXIII.
N. Robertson, P. Seymour, R. Thomas: Quickly Excluding a Planar Graph, J. Comb. Theory, Ser. B (1994), 323-348.
C. Thomassen: A simpler proof of the excluded minor theorem for higher surfaces, J.Combinatorial Theory B 70 (1997), 306-311.
K. Kawarabayashi, P. Wollan: A simpler algorithm and shorter proof for the graph minor decomposition, STOC 2011, 451-458.
M. Grohe, K. Kawarabayashi, D. Marx, P. Wollan: Finding topological subgraphs is fixed-parameter tractable, STOC 2011, 479-488.
R. Diestel, T. Jensen, K. Gorbunov, C. Thomassen: Highly Connected Sets and the Excluded Grid Theorem, J. Comb. Theory, Ser. B (1999), 61-73.