Graph minors. X: Obstructions to tree-decomposition.

*(English)*Zbl 0764.05069[For Part IX see ibid. 49, No. 1, 40-77 (1990; Zbl 0741.05044)].

The paper studies hypergraphs. A tree-decomposition of a hypergraph is described; its substance is piecing small hypergraphs together in a tree structure. By means of this concept the tree-width of a hypergraph is defined. The obstructions to the existence of such a tree structure are studied. Important concepts are a separation and a tangle. A separation of a hypergraph \(G\) is a pair of its subhypergraphs whose intersection has no edges and whose union is \(G\). Tangles are certain systems of separations. The content of this paper can be illustrated by listing the titles of its sections: 1. Tangles, 2. Some tangle lemmas, 3. A lemma about submodular functions, 4. Branch-width, 5. Branch-width and tree- width, 6. New tangles from old, 7. A tangle in a grid, 8. Robust and titanic separations, 9. Laminar separations, 10. Tangle tree- decompositions, 11. Structure relative to a tangle, 12. Tangles and matroids.

The paper studies hypergraphs. A tree-decomposition of a hypergraph is described; its substance is piecing small hypergraphs together in a tree structure. By means of this concept the tree-width of a hypergraph is defined. The obstructions to the existence of such a tree structure are studied. Important concepts are a separation and a tangle. A separation of a hypergraph \(G\) is a pair of its subhypergraphs whose intersection has no edges and whose union is \(G\). Tangles are certain systems of separations. The content of this paper can be illustrated by listing the titles of its sections: 1. Tangles, 2. Some tangle lemmas, 3. A lemma about submodular functions, 4. Branch-width, 5. Branch-width and tree- width, 6. New tangles from old, 7. A tangle in a grid, 8. Robust and titanic separations, 9. Laminar separations, 10. Tangle tree- decompositions, 11. Structure relative to a tangle, 12. Tangles and matroids.

Reviewer: B.Zelinka (Liberec)

##### MSC:

05C65 | Hypergraphs |

05C05 | Trees |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

05B35 | Combinatorial aspects of matroids and geometric lattices |

PDF
BibTeX
XML
Cite

\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 52, No. 2, 153--190 (1991; Zbl 0764.05069)

Full Text:
DOI

##### References:

[1] | Dirac, G.A, (), 61-85 |

[2] | Robertson, N; Seymour, P.D, Graph minors. IV. tree-width and well-quasi-ordering, J. combin. theory ser. B, 48, 227-254, (1990) · Zbl 0719.05032 |

[3] | Robertson, N; Seymour, P.D, Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055 |

[4] | Robertson, N; Seymour, P.D, Graph minors. VIII. A Kuratowski theorem for general surfaces, J. combin. theory ser. B, 48, 255-288, (1990) · Zbl 0719.05033 |

[5] | \scN. Robertson and P. D. Seymour, Graph minors. XII. Circuits on a surface, submitted for publication. · Zbl 0840.05016 |

[6] | \scN. Robertson and P. D. Seymour, Graph minors. XVII. Excluding a non-planar graph, submitted for publication. · Zbl 1023.05040 |

[7] | \scN. Robertson, P. D. Seymour, and R. Thomas, Quickly excluding a planar graph, submitted for publication. · Zbl 0807.05023 |

[8] | Welsh, D.J.A, () |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.