zbMATH — the first resource for mathematics

On tree-partitions of graphs. (English) Zbl 0844.05078
A graph \(G\) admits a tree-partition of width \(k\) if its vertex set can be partitioned into sets of size at most \(k\) so that the graph obtained by identifying the vertices in each set of the partition, and then deleting loops and parallel edges, is a forest. If no such \(k\) exist, the width is set to be infinite. The main result of the paper provides that a graph \(G\) does not admit a tree-partition of small width iff \(G\) contains a subgraph isomorphic to a subdivision of a large member from any of the four specified (infinite) families of finite graphs. Similar result concerning characterization of graphs, which admit a tree-partition such that each set of the partition is finite, was obtained by Halin. It is also formulated in the terms of exclusion of three infinite specific graphs. However, as the authors show, just excluding finite versions of Halin’s graphs is necessary but not sufficient for bounding the tree-partition width.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs
05C35 Extremal problems in graph theory
05C05 Trees
Full Text: DOI
[1] G. Ding and B. Oporowski, Some results on tree decomposition of graphs, J. Graph Theory, to appear. · Zbl 0837.05044
[2] Halin, R., Tree-partitions of infinite graphs, Discrete math., 97, 203-217, (1991) · Zbl 0763.05027
[3] Křiz, I.; Thomas, R., The Menger-like property of the tree-width of infinite graphs, J. combin. theory ser. B, 52, 86-91, (1991) · Zbl 0675.05046
[4] Robertson, N.; Seymour, P., Graph minors. III. planar tree-width, J. combin. theory ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[5] Robertson, N.; Seymour, P., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[6] N. Robertson, P. Seymour and R. Thomas, Quickly excluding a planar graph, submitted. · Zbl 0807.05023
[7] Seese, D., Tree-partite graphs and the complexity of algorithms, () · Zbl 0574.68036
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.