pith. sign in

arxiv: 1609.09098 · v1 · pith:4FOTTEENnew · submitted 2016-09-28 · 🧮 math.CO

A generalization of the Grid Theorem

classification 🧮 math.CO
keywords thetagraphstree-widthcliquegraphgridobtainedsequence
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. An Overview of Universal Obstructions for Graph Parameters

    cs.DM 2023-04 unverdicted novelty 3.0

    The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.