Pith. sign in

REVIEW 1 cited by

Separating layered treewidth and row treewidth

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2105.01230 v3 pith:ZBGCBEXK submitted 2021-05-04 math.CO cs.DM

classification math.COcs.DM
keywords treewidthlayeredboundedgraphbeenopenpathwidthanalogous
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Row pathwidth of complete binary trees

    math.CO 2026-08 accept novelty 8.0 of 10

    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.

Pith tools