Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
复制标题
归纳子图和树分解 II。
DOI：
10.1016/j.jctb.2023.10.005
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kristina Vuvskovi'c
中科院分区：
文献类型：
--
作者：
Tara Abrishami;M. Chudnovsky;Cemil Dibek;Sepehr Hajebi;Pawel Rzka.zewski;S. Spirkl;Kristina Vuvskovi'c
本文研究的问题是：什么是大树宽图的不可避免导出子图？Aboulker等人提出了一个猜想，在有界最大度的图中回答了这个问题，声称对所有k和Δ，每个最大度至多为Δ且树宽足够大的图包含（k × k）-壁的一个细分或（k× k）-壁的一个细分的线图作为导出子图。我们证明两个定理支持这个猜想，如下。1.当t≥ 2时，一个t-theta是一个由两个不相邻的顶点和它们之间的三条内部顶点不相交的路组成的图，每条路的长度至少为t。一个t-金字塔是由一个顶点v，一个与v不相交的三角形B和三条从v开始的顶点不相交的路组成的图，每条路将v连接到B的一个顶点，每条路的长度至少为t。证明了对任意的k，t和Δ，每一个最大度不超过Δ且树宽足够大的图都包含一个t-θ，或一个t-金字塔，或（k× k）-壁的一个细分的线图作为导出子图.这肯定地回答了Pilipczuk等人的一个问题，即是否每个有界最大度和足够大树宽的图都包含一个theta或一个三角形作为导出子图（其中theta意味着对于某些t≥ 2的t-theta）。2.一个次三次细分毛毛虫是一个最大度至多为3的树，它的所有三度顶点都在一条路上.我们证明了：对于每一个Δ和次三次细分毛毛虫T，每一个最大度至多为Δ且树宽足够大的图都包含T的一个细分或T的一个细分的线图作为诱导子图.
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all k and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of the (k× k)-wall or the line graph of a subdivision of the (k× k)-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For t≥ 2, a t-theta is a graph consisting of two nonadjacent vertices and three internally vertex-disjoint paths between them, each of length at least t. A t-pyramid is a graph consisting of a vertex v, a triangle B disjoint from v and three paths starting at v and vertex-disjoint otherwise, each joining v to a vertex of B, and each of length at least t. We prove that for all k, t and Δ, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a t-theta, or a t-pyramid, or the line graph of a subdivision of the (k× k)-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a t-theta for some t≥ 2). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every Δ and subcubic subdivided caterpillar T, every graph with maximum degree at most Δ and sufficiently large treewidth contains either a subdivision of T or the line graph of a subdivision of T as an induced subgraph.
归纳子图和树分解 I. 有界度的偶孔无图
DOI：
10.1016/j.jctb.2022.05.009
发表时间：
2022
期刊：
Series B
影响因子：
--
作者：
Abrishami, Tara;Chudnovsky, Maria;Vušković, Kristina
通讯作者：
Vušković, Kristina
归纳子图和树分解 III。
影响因子：
--
作者：
Chudnovsky, Maria;Abrishami, Tara;Hajebi, Sepehr;Spirkl, Sophie
通讯作者：
Spirkl, Sophie
无长诱导爪有界度图中最大独立集的多项式时间算法
DOI：
--
发表时间：
2022
期刊：
2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
--
作者：
Chudnovsky, M. with
通讯作者：
Chudnovsky, M. with