An Overview To The Excluded Grid Theorem

A survey of Robertson and Seymour's Excluded Grid Theorem, working through Julia Chuzhoy's improved and simplified proof and the techniques it rests on.

An Overview To The Excluded Grid Theorem
Years2015VenueRWTH Aachen — i1, GroheKindSeminar paperPaperDownload PDF →

Abstract

This paper summarizes the proceeding of Robertson and Seymour’s so-called Excluded Grid Theorem. It states the existence of a bound of treewidth for a graph not to contain a grid of specified size as a minor. While recent research on this topic has improved far forward, we focus on a recent paper from Julia Chuzhoy showing a new, improved, and simplified proof, working out essential concepts and techniques used by her and other referenced publications.