Graph minors. III. Planar tree-width.

*(English)*Zbl 0548.05025[For part I see ibid. 35, 39-61 (1983; Zbl 0521.05062.]

This paper continues the important work by the authors on graph minors. A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contraction. The tree decomposition of a graph G is a pair (T,X) where T is a tree and X is a family of subsets of V(G): \(X=\{X_ t:\quad t\in V(T)\}\) such that (i) the union of the \(X_ t\) is V(G); (ii) for every edge e of G, there exists an \(X_ t\) containing both ends of e; and (iii) for t, t’, t”\(\in V(T)\), if t’ is on the path of T between t and t”, then \(X_ t\cap X_{t''}\subseteq X_{t'}.\) The width of the tree decomposition is the maximum of \(| X_ t| -1.\) The graph G has tree-width w if w is the minimum width of any tree decomposition of G. The author’s main result is: For every planar graph H, there is a number w such that every planar graph with no minor isomorphic to H has tree- width \(\leq w\).

This paper continues the important work by the authors on graph minors. A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contraction. The tree decomposition of a graph G is a pair (T,X) where T is a tree and X is a family of subsets of V(G): \(X=\{X_ t:\quad t\in V(T)\}\) such that (i) the union of the \(X_ t\) is V(G); (ii) for every edge e of G, there exists an \(X_ t\) containing both ends of e; and (iii) for t, t’, t”\(\in V(T)\), if t’ is on the path of T between t and t”, then \(X_ t\cap X_{t''}\subseteq X_{t'}.\) The width of the tree decomposition is the maximum of \(| X_ t| -1.\) The graph G has tree-width w if w is the minimum width of any tree decomposition of G. The author’s main result is: For every planar graph H, there is a number w such that every planar graph with no minor isomorphic to H has tree- width \(\leq w\).

Reviewer: A.Tucker

PDF
BibTeX
Cite

\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 36, 49--64 (1984; Zbl 0548.05025)

Full Text:
DOI

##### References:

[1] | Robertson, N; Seymour, P.D, Graph minors. I. excluding a forest, J. combin. theory ser. B, 35, 39-61, (1983) · Zbl 0521.05062 |

[2] | {\scN. Robertson and P. D. Seymour}, Graph minors. II. Algorithmic aspects of tree-width, submitted. · Zbl 0611.05017 |

[3] | {\scN. Robertson and P. D. Seymour}, Graph minors. IV. Tree-width and well-quasiordering, submitted. · Zbl 0719.05032 |

[4] | {\scN. Robertson and P. D. Seymour}, Graph minors. V. Excluding a planar graph, submitted. · Zbl 1023.05040 |

[5] | {\scN. Robertson and P. D. Seymour}, Graph minors. VI. Disjoint paths on a surface, in preparation. · Zbl 0658.05044 |

[6] | {\scN. Robertson and P. D. Seymour}, Graph minors. VII. Disjoint paths on a surface, in preparation. · Zbl 0658.05044 |

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.