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 |
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, (Combinatorial Theory and Its Applications II. Combinatorial Theory and Its Applications II, Proc. Colloq. Balatonfured (1969)), 571-584 · Zbl 0208.52202 |
| [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] | Neil Robertson and P. D. SeymourJ. Algorithms; Neil Robertson and P. D. SeymourJ. Algorithms · Zbl 0611.05017 |
| [11] | Neil Robertson and P. D. Seymour; Neil Robertson and P. D. Seymour |
| [12] | Neil Robertson and P. D. Seymour; Neil Robertson and P. D. Seymour · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
