# zbMATH — the first resource for mathematics

Graph searching and a min-max theorem for tree-width. (English) Zbl 0795.05110
Summary: 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+1$$ 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 $$\leq k$$ vertices meets all of them. A corollary is an analogue of LaPaugh’s “monotone search” theorem for cops trapping a roober they can see (LaPaugh’s robber was invisible).

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C05 Trees 91A43 Games involving graphs
Full Text: