A generalization of the Grid Theorem

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 $θ$, defining the $θ$-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 $θ$. We find the unavoidable minors for the graphs with large $θ$-tree-width and we obtain Robertson and Seymour's Grid Theorem as a corollary.

No reviews yet.

No comments yet.