Separating layered treewidth and row treewidth
arXiv:2105.01230 · doi:10.46298/dmtcs.7458
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 we describe a graph with layered treewidth 1 and row treewidth . We also prove an analogous result for layered pathwidth and row pathwidth.
References in corpus (17)
- Characterisations and Examples of Graph Classes with Bounded Expansion
- Layered Separators in Minor-Closed Graph Classes with Applications
- Improper Colourings inspired by Hadwiger's Conjecture
- Improved bounds for centered colorings
- Track Layouts, Layered Path Decompositions, and Leveled Planarity
- Planar graphs have bounded nonrepetitive chromatic number
- Sparse universal graphs for planarity
- Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
- Better bounds for poset dimension and boxicity
- Clustered Graph Coloring and Layered Treewidth
- Notes on Graph Product Structure Theory
- Minor-closed graph classes with bounded layered pathwidth
- New representation results for planar graphs
- Clustered Coloring of Graphs Excluding a Subgraph and a Minor
- Graph product structure for non-minor-closed classes
- Asymptotically Optimal Vertex Ranking of Planar Graphs
- Queue Layouts of Graphs with Bounded Degree and Bounded Genus