Graph minors. V. Excluding a planar graph.

*(English)*Zbl 0598.05055[For part I see the authors’ paper ibid. 35, 39-61 (1983; Zbl 0521.05062), for part III see their paper ibid. 36, 49-64 (1984; Zbl 0548.05025), for part VI see ibid., 115-138 (1986; Zbl 0598.05042). See also their survey paper in Surveys in Combinatorics 1985, Pap. 10th Br. Combin. Conf., Glasgow/Scotl. 1985, Lond. Math. Soc. Lect. Note Ser. 103, 153-171 (1985; Zbl 0568.05025).]

Minors of graphs are obtained by contraction of subgraphs. A decomposition of a graph is a covering of both the vertices and edges by subgraphs, considered as a graph by connecting any two meeting pieces.

It is shown that for each planar graph H there exists a number w such that any graph with no minor isomorphic to H admits a tree-decomposition with pieces of cardinality at most w. In fact this is proven first for H being a finite dimensional grid. As any planar graph is the minor of some such grid, the final result is obtained.

Some consequences are as follows: There is no infinite family of graphs containing a planar one, and in which no graph is isomorphic to a minor of another one. Deciding whether a graph admits a fixed planar graph as a minor, is polynomially solvable. There is a characterization of planar graphs as those graphs which satisfy a property analogous to the one shown by Erdős and Posa for circuits.

Minors of graphs are obtained by contraction of subgraphs. A decomposition of a graph is a covering of both the vertices and edges by subgraphs, considered as a graph by connecting any two meeting pieces.

It is shown that for each planar graph H there exists a number w such that any graph with no minor isomorphic to H admits a tree-decomposition with pieces of cardinality at most w. In fact this is proven first for H being a finite dimensional grid. As any planar graph is the minor of some such grid, the final result is obtained.

Some consequences are as follows: There is no infinite family of graphs containing a planar one, and in which no graph is isomorphic to a minor of another one. Deciding whether a graph admits a fixed planar graph as a minor, is polynomially solvable. There is a characterization of planar graphs as those graphs which satisfy a property analogous to the one shown by Erdős and Posa for circuits.

Reviewer: F.Plastria

##### MSC:

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

05C05 | Trees |

PDF
BibTeX
XML
Cite

\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 41, 92--114 (1986; Zbl 0598.05055)

Full Text:
DOI

##### References:

[1] | Bergmann, H, Ein planaritätskriterium für endliche graphen, Elem. math., 37, 49-51, (1982) · Zbl 0484.05032 |

[2] | Buneman, P, A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128 |

[3] | Dirac, G.A, On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703 |

[4] | Erdös, P; Pósa, L, On independent circuits contained in a graph, Canad. J. math., 17, 347-352, (1965) · Zbl 0129.39904 |

[5] | Gavril, F, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101 |

[6] | Gyárfás, A; Lehel, J, A Helly-type problem in trees, (), 571-584 |

[7] | Györi, E, On the division of graphs to connected subgraphs, Combinatorics, colloq. math. soc. János bolyai, 18, 485-494, (1978) · Zbl 0388.05008 |

[8] | Lovász, L, A homology theory for spanning trees of a graph, Acta math. acad. sci. hungar., 30, 241-251, (1977) · Zbl 0403.05040 |

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

[10] | \scNeil Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, in press. · Zbl 0611.05017 |

[11] | \scNeil Robertson and P. D. Seymour, Graph minors. IV. Tree-width and well-quasiordering, submitted for publication. |

[12] | \scNeil Robertson and P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, submitted for publication. · Zbl 0658.05044 |

[13] | Tutte, W.T, From matrices to graphs, Canad. J. math., 16, 108-127, (1964) · Zbl 0138.19202 |

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.