Abstract:
Tree decomposition is a construction in graph theory that makes it possible to analyze how much like a tree a graph is. The Graph Minor Theorem (Robertson-Seymour) states that in any infinite collection of graphs there is a pair such that one is a minor of the other. I will explain tree decompositions and tree width and give some idea of how they are used in the proof of GMT.

(This seminar is part of the requirement for the PhD-course in Graph Theory and will follow chapter 12 of Diestel's book.)