A generalization of the Grid Theorem

Publication date 28 September 2016

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

h e t a

, defining the

h e t a

-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

h e t a

. We find the unavoidable minors for the graphs with large

h e t a

-tree-width and we obtain Robertson and Seymour's Grid Theorem as a corollary.

This page was built for publication: A generalization of the Grid Theorem