Back to Search Start Over

Separating layered treewidth and row treewidth

Authors :
Bose, Prosenjit
Dujmović, Vida
Javarsineh, Mehrnoosh
Morin, Pat
Wood, David R.
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.

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