### 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 language | English (US) |
---|---|

Pages (from-to) | 22-33 |

Number of pages | 12 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 58 |

Issue number | 1 |

DOIs | |

State | Published - May 1993 |

Externally published | Yes |

### 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

Seymour, P. D., & Thomas, R. (1993). Graph Searching and a Min-Max Theorem for Tree-Width.

*Journal of Combinatorial Theory, Series B*,*58*(1), 22-33. https://doi.org/10.1006/jctb.1993.1027