On tree-partitions of graphs (Q1910567): Difference between revisions

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.