Partitioning graphs of bounded tree-width (Q1307308)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1354839
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Partitioning graphs of bounded tree-width |
scientific article; zbMATH DE number 1354839 |
Statements
Partitioning graphs of bounded tree-width (English)
0 references
31 October 1999
0 references
This paper studies vertex partitions and edge partitions of graphs of bounded tree-width into graphs of smaller tree-width. First the existence of several kinds of such partitions is proved. Then it is shown that some of the results of the first part are close to being best possible. Finally a result on partitioning graphs of bounded tree-width into star-forests is described.
0 references
tree-width
0 references
coloring
0 references
partitions
0 references
star-forests
0 references
0.8526918888092041
0 references
0.8381386995315552
0 references
0.8168336153030396
0 references
0.8107163310050964
0 references
