论文标题
次要封闭图类别及以后的长期诱导路径
Long induced paths in minor-closed graph classes and beyond
论文作者
论文摘要
在本文中，我们显示的每个路径的图形小于$ k $的订单$ n $的$ k $也具有至少$ \ frac {1} {3} {3} n^{1/k} $的诱导路径。这是Esperet，Lemoine and Maffray（2016）获得的界限数字的指数改进和概括的概括。我们将此结果与上限进行补充。 然后使用该结果证明以下两个概括： - 小于$ k $的每图treewidth $ n $的$ k $都包含一个诱导的顺序路径，至少$ \ frac {1} {4} {4} {\ log n）^{1/k} $; - 对于每个在拓扑未成年人中关闭的非平凡的图形类都有一个常数$ d \ in（0,1）$，使得该类的每个图形都具有订单$ n $的路径均包含诱导的订单途径至少$（\ log log n）^d $。 我们还描述了这些结果的后果，而不是拓扑未成年人关闭的图形类别。
In this paper we show that every graph of pathwidth less than $k$ that has a path of order $n$ also has an induced path of order at least $\frac{1}{3} n^{1/k}$. This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by Esperet, Lemoine and Maffray (2016) for interval graphs of bounded clique number. We complement this result with an upper-bound. This result is then used to prove the two following generalizations: - every graph of treewidth less than $k$ that has a path of order $n$ contains an induced path of order at least $\frac{1}{4} (\log n)^{1/k}$; - for every non-trivial graph class that is closed under topological minors there is a constant $d \in (0,1)$ such that every graph from this class that has a path of order $n$ contains an induced path of order at least $(\log n)^d$. We also describe consequences of these results beyond graph classes that are closed under topological minors.
