标题： 图中的长诱导路径 显示英文标题

标题： Long induced paths in graphs

摘要： 我们证明了每个具有$n$个顶点的3连通平面图包含一个由$\Omega(\log n)$个顶点组成的诱导路径，这是最佳的，并且将已知的最佳下界提高了乘法因子$\log \log n$。 我们推导出任何平面图（或更一般地，任何可嵌入固定曲面的图）如果包含一个由$n$个顶点组成的路径，也包含一个由$\Omega(\sqrt{\log n})$个顶点组成的诱导路径。 我们猜想，对于任何$k$，存在一个常数$c(k)$，使得任何具有长度为$n$的路径的$k$-退化图也包含一个长度为$\Omega((\log n)^{c(k)})$的诱导路径。 我们提供了例子表明这个数量级是最佳可能的（即使对于弦图而言），并且证明了在区间图的情况下该猜想成立。 显示英文摘要

摘要： We prove that every 3-connected planar graph on $n$ vertices contains an induced path on $\Omega(\log n)$ vertices, which is best possible and improves the best known lower bound by a multiplicative factor of $\log \log n$. We deduce that any planar graph (or more generally, any graph embeddable on a fixed surface) with a path on $n$ vertices, also contains an induced path on $\Omega(\sqrt{\log n})$ vertices. We conjecture that for any $k$, there is a contant $c(k)$ such that any $k$-degenerate graph with a path on $n$ vertices also contains an induced path on $\Omega((\log n)^{c(k)})$ vertices. We provide examples showing that this order of magnitude would be best possible (already for chordal graphs), and prove the conjecture in the case of interval graphs.