Geodesic
Separating layered treewidth and row treewidth
Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.7458
Classification : 05C10 
@article{DMTCS_2022_24_1_a16,
     author = {Bose, Prosenjit and Dujmovi\'c, Vida and Javarsineh, Mehrnoosh and Morin, Pat and Wood, David R.},
     title = {Separating layered treewidth and row treewidth},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2022},
     doi = {10.46298/dmtcs.7458},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7458/}
}
TY  - JOUR
AU  - Bose, Prosenjit
AU  - Dujmović, Vida
AU  - Javarsineh, Mehrnoosh
AU  - Morin, Pat
AU  - Wood, David R.
TI  - Separating layered treewidth and row treewidth
JO  - Discrete mathematics & theoretical computer science
PY  - 2022
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7458/
DO  - 10.46298/dmtcs.7458
LA  - en
ID  - DMTCS_2022_24_1_a16
ER  - 
%0 Journal Article
%A Bose, Prosenjit
%A Dujmović, Vida
%A Javarsineh, Mehrnoosh
%A Morin, Pat
%A Wood, David R.
%T Separating layered treewidth and row treewidth
%J Discrete mathematics & theoretical computer science
%D 2022
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7458/
%R 10.46298/dmtcs.7458
%G en
%F DMTCS_2022_24_1_a16
Bose, Prosenjit; Dujmović, Vida; Javarsineh, Mehrnoosh; Morin, Pat; Wood, David R. Separating layered treewidth and row treewidth. Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1. doi : 10.46298/dmtcs.7458. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7458/

Cité par Sources :