Abstract

How many colors needs a minor? -- What looks like a question of a curious kid with a coloring book, is in fact one of the most important open problems in graph theory. In this talk I will first discuss the concept of a minor and his relative, the tree-width, and then talk about a result that many consider to be one of the cornerstones of graph theory.