A generalization of the Grid Theorem

Abstract

A graph has tree-width at most $k$ if it can be obtained from a set of graphs each with at most $k+1$ vertices by a sequence of clique sums. We refine this definition by, for each non-negative integer $\theta$, defining the $\theta$-tree-width of a graph to be at most $k$ if it can be obtained from a set of graphs each with at most $k+1$ vertices by a sequence of clique sums on cliques of size less than $\theta$. We find the unavoidable minors for the graphs with large $\theta$-tree-width and we obtain Robertson and Seymour's Grid Theorem as a corollary.

27 pages, 5 figures

Cited by in corpus (1)

• A unified treatment of linked and lean tree-decompositions