### Abstract

Roughly, a graph has small "tree-width" if it can be constructed by piecing small graphs together in a tree structure. Here we study the obstructions to the existence of such a tree structure. We find, for instance: 1. (i) a minimax formula relating tree-width with the largest such obstructions 2. (ii) an association between such obstructions and large grid minors of the graph 3. (iii) a "tree-decomposition" of the graph into pieces corresponding with the obstructions. These results will be of use in later papers.

Original language | English (US) |
---|---|

Pages (from-to) | 153-190 |

Number of pages | 38 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 52 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 1991 |

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 minors. X. Obstructions to tree-decomposition'. Together they form a unique fingerprint.

## Cite this

Robertson, N., & Seymour, P. D. (1991). Graph minors. X. Obstructions to tree-decomposition.

*Journal of Combinatorial Theory, Series B*,*52*(2), 153-190. https://doi.org/10.1016/0095-8956(91)90061-N