Prosenjit Bose ; Vida Dujmović ; Mehrnoosh Javarsineh ; Pat Morin ; David R. Wood - Separating layered treewidth and row treewidth

dmtcs:7458 - Discrete Mathematics & Theoretical Computer Science, May 13, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.7458
Separating layered treewidth and row treewidthArticle

Authors: Prosenjit Bose ; Vida Dujmović ; Mehrnoosh Javarsineh ; Pat Morin ; David R. Wood

    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.

    https://doi.org/10.46298/dmtcs.7458
    Source: arXiv.org:2105.01230
    Volume: vol. 24, no. 1
    Section: Graph Theory
    Published on: May 13, 2022
    Accepted on: April 12, 2022
    Submitted on: May 5, 2021
    Keywords: Mathematics - Combinatorics, Computer Science - Discrete Mathematics
    Licence: Attribution 4.0 International (CC BY 4.0)
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Publications

    Has review
    • 1 zbMATH Open

    Share and export

    Consultation statistics

    This page has been seen 1180 times.
    This article's PDF has been downloaded 1087 times.