Graphs of linear growth have bounded treewidth (Q6115513): Difference between revisions
From MaRDI portal
Latest revision as of 13:10, 2 August 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
0 references