Back to Search
Start Over
Separating layered treewidth and row treewidth
- Source :
- Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Graph Theory (May 13, 2022) dmtcs:7458
- Publication Year :
- 2021
-
Abstract
- Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. It follows from the definitions that the layered treewidth of a graph is at most its row treewidth plus 1. Moreover, a minor-closed class has bounded layered treewidth if and only if it has bounded row treewidth. However, it has been open whether row treewidth is bounded by a function of layered treewidth. This paper answers this question in the negative. In particular, for every integer $k$ we describe a graph with layered treewidth 1 and row treewidth $k$. We also prove an analogous result for layered pathwidth and row pathwidth.
- Subjects :
- Mathematics - Combinatorics
Computer Science - Discrete Mathematics
Subjects
Details
- Database :
- arXiv
- Journal :
- Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Graph Theory (May 13, 2022) dmtcs:7458
- Publication Type :
- Report
- Accession number :
- edsarx.2105.01230
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.46298/dmtcs.7458