Pith. sign in

Separating layered treewidth and row treewidth

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2026 1

verdicts

ACCEPT 1

roles

background 1

polarities

background 1

representative citing papers

Row pathwidth of complete binary trees

math.CO · 2026-08-10 · accept · novelty 8.0

The row pathwidth of the height-h complete binary tree is at least floor((h+1)/16), so it grows linearly with h and matches the general upper bound up to constants.

citing papers explorer

Showing 1 of 1 citing paper.

  • Row pathwidth of complete binary trees math.CO · 2026-08-10 · accept · none · ref 1 · internal anchor

    The row pathwidth of the height-h complete binary tree is at least floor((h+1)/16), so it grows linearly with h and matches the general upper bound up to constants.