A generalization of the Grid Theorem
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
An Overview of Universal Obstructions for Graph Parameters
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.