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.


翻译:最近引入了图形参数,这些参数一直是解决几个众所周知的公开问题的关键成分。根据定义,图层树枝最多是其一行树枝加1。此外,一个次要封闭的类别已经将树枝捆绑在一起,如果并且只有将一行树枝捆绑在一起。然而,已经打开了树枝是否被一行树枝捆绑的功能所捆绑。本文否定了这个问题。特别是,我们用每整数一美元描述一个图,用一行树枝1和一行树枝加1美元。我们证明,对于分层的路径和一行的路径,我们也有相似的结果。

0
下载
关闭预览

相关内容

【干货书】实体搜索,Entity-Oriented Search,358页pdf
专知会员服务
34+阅读 · 2021年4月9日
【Manning新书】现代Java实战,592页pdf
专知会员服务
99+阅读 · 2020年5月22日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
一文读懂Faster RCNN
极市平台
5+阅读 · 2020年1月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Faster R-CNN
数据挖掘入门与实战
4+阅读 · 2018年4月20日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年7月1日
Backgammon is Hard
Arxiv
0+阅读 · 2021年6月30日
Arxiv
15+阅读 · 2021年2月19日
Arxiv
8+阅读 · 2020年10月9日
VIP会员
相关VIP内容
相关资讯
一文读懂Faster RCNN
极市平台
5+阅读 · 2020年1月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Faster R-CNN
数据挖掘入门与实战
4+阅读 · 2018年4月20日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员