Skip to main content
1 of 3
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

One possible generalization comes from the graph minors project of Robertson and Seymour. In particular the notion of tree-width is in some sense dual to the notion of a bramble (I will define this in a second). Note that a connected graph has tree-width 1 if and only if it is a tree, so this is indeed a generalization of acyclicity.

Now, let $G$ be a graph. Two subsets of $V(G)$ touch if they have a vertex in common or $G$ contains an edge between them. A set of pairwise touching connected vertex sets in $G$ is a bramble. A subset of vertices covers a bramble $\mathcal{B}$ if it intersects every set in $\mathcal{B}$. The least number of vertices covering $\mathcal{B}$ is the order of $\mathcal{B}$.

Here is the duality relation that I alluded to earlier.

Theorem. A graph has tree-width $< k$ if and only if it does not contain a bramble of order $>k$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187