On tree-partitions of graphs (Q1910567): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some results on tree decomposition of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tree-partitions of infinite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Menger-like property of the three-width of infinite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. III. Planar tree-width / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. V. Excluding a planar graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Quickly excluding a planar graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3692864 / rank | |||
Normal rank |
Latest revision as of 11:14, 24 May 2024
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