Graphs of linear growth have bounded treewidth (Q6115513): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 06:20, 10 July 2024
scientific article; zbMATH DE number 7725117
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Graphs of linear growth have bounded treewidth |
scientific article; zbMATH DE number 7725117 |
Statements
Graphs of linear growth have bounded treewidth (English)
0 references
10 August 2023
0 references
Summary: A graph class \(\mathcal{G}\) has linear growth if, for each graph \(G \in \mathcal{G}\) and every positive integer \(r\), every subgraph of \(G\) with radius at most \(r\) contains \(O(r)\) vertices. In this paper, we show that every graph class with linear growth has bounded treewidth.
0 references
tree-decomposition of a graph
0 references
\(k\)-stack layout
0 references
