论文标题
诱导的子图和路径分解
Induced subgraphs and path decompositions
论文作者
论文摘要
图形$ h $是图形$ g $的诱导子图，如果图形到$ h $可以通过删除顶点从$ g $获得。最近，人们对理解大宽度图的不可避免的诱导子图引起了巨大兴趣。在这项工作的激励下，我们考虑了路径宽的类似问题：不可避免的大路径宽度图的诱发子图是什么？在一般环境中解决这个问题看起来充满挑战时，我们证明了稀疏图的各种结果。特别是，我们表明，每个具有界限最大程度和足够大的路径的图形都包含大型完整的二进制树的细分或大型完整二进制树的细分的线图，作为诱导的子图。同样，我们表明，每个图形不包括固定的未成年人，并且具有足够大的路径宽，包含大型完整二进制树的细分或大型完整二进制树的细分的线图作为诱导的子图。最后，我们给出了一个特征，以何时由有限的禁止诱导子图定义的遗传阶级具有有限的路径。
A graph $H$ is an induced subgraph of a graph $G$ if a graph isomorphic to $H$ can be obtained from $G$ by deleting vertices. Recently, there has been significant interest in understanding the unavoidable induced subgraphs for graphs of large treewidth. Motivated by this work, we consider the analogous problem for pathwidth: what are the unavoidable induced subgraphs for graphs of large pathwidth? While resolving this question in the general setting looks challenging, we prove various results for sparse graphs. In particular, we show that every graph with bounded maximum degree and sufficiently large pathwidth contains a subdivision of a large complete binary tree or the line graph of a subdivision of a large complete binary tree as an induced subgraph. Similarly, we show that every graph excluding a fixed minor and with sufficiently large pathwidth contains a subdivision of a large complete binary tree or the line graph of a subdivision of a large complete binary tree as an induced subgraph. Finally, we present a characterisation for when a hereditary class defined by a finite set of forbidden induced subgraphs has bounded pathwidth.
