On tree-partitions of graphs (Q1910567)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On tree-partitions of graphs |
scientific article |
Statements
On tree-partitions of graphs (English)
0 references
25 March 1996
0 references
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.
0 references
infinite graphs
0 references
graph minors
0 references
tree-partition
0 references
width
0 references
forest
0 references
characterization
0 references