Graph Searching and a Min-Max Theorem for Tree-Width

P. D. Seymour, Robin Thomas

Research output: Contribution to journalArticle

232 Scopus citations

Abstract

The tree-width of a graph G is the minimum k such that G may be decomposed into a “tree-structure” of pieces each with at most k + l vertices. We prove that this equals the maximum k such that there is a collection of connected subgraphs, pairwise intersecting or adjacent, such that no set of ≤ k vertices meets all of them. A corollary is an analogue of LaPaugh’s “monotone search” theorem for cops trapping a robber they can see (LaPaugh′s robber was invisible).

Original languageEnglish (US)
Pages (from-to)22-33
Number of pages12
JournalJournal of Combinatorial Theory, Series B
Volume58
Issue number1
DOIs
StatePublished - May 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Graph Searching and a Min-Max Theorem for Tree-Width'. Together they form a unique fingerprint.

  • Cite this