Teorie grafových minorů

Aktuálně tento předmět nevyučuji.

Obsah přednášek
  1. Opakovani, definice, hlavni myslenky a ingredience dukazu strukturalni vety.
  2. Stromova sirka a tangle.
  3. Velka stromova sirka vynucuje velkou zed.
  4. Tangle a metrika na plochach.
  5. Plochy a linkovani.
  6. Two Short Proofs Concerning Tree-Decompositions
  7. 2-linkage a jejich zobecneni (transakce).
  8. Rozsirovani vnoreni.
  9. Strukturalni veta.
  10. Testovani existence minoru.
  11. Stromove rozklady a dobre usporadani.
  12. Plochy a dobre usporadani.
  13. Wagnerova hypoteza.
Další materiály a zdroje

Doporučená literatura

  • 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.
  • Julia Chuzhoy: Improved Bounds for the Flat Wall Theorem. SODA 2015: 256-275.

Další zdroje