论文标题
在没有抗完整周期的图中引起的路径
Induced paths in graphs without anticomplete cycles
论文作者
论文摘要
让我们说图是$ s \ natercal {o} $ - 免费，其中$ s \ ge 1 $是整数，如果不存在$ s $ cycles the Graph的$ s $周期，它们是成对的顶点disjoint，并且没有边缘连接的边缘。即使$ s = 2 $，此类图的结构也不是很好的理解。例如，到目前为止，我们还不知道如何测试图形是否为$ 2 \ Mathcal {o} $ - 在多项式时间内免费；由于ngoc khang le，有一个开放的猜想，即$ 2 \ mathcal {o} $ - 免费图形只有一个多项式的诱导路径。 在本文中，我们证明了Le的猜想；实际上，我们将证明，对于所有$ s \ ge 1 $，存在$ c> 0 $，这样每一个$ s \ mathcal {o} $ - 免费图$ g $最多都有$ | g |^c $诱导的路径。这提供了一种多时间算法来测试图形是否为$ s \ Mathcal {o} $ - 免费，对于所有固定$ s $。 证明有三个部分。首先，由于LE，有一个简短而美丽的证据，这将问题减少到没有长度为四个循环的图形上证明了同一件事。 Second, there is a recent result of Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek, that in every $s\mathcal{O}$-free graph $G$ with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in $|G|$.第三，有一个论证使用Bonamy等人的结果。推断定理。最后一个是本文的主要内容。
Let us say a graph is $s\mathcal{O}$-free, where $s\ge 1$ is an integer, if there do not exist $s$ cycles of the graph that are pairwise vertex-disjoint and have no edges joining them. The structure of such graphs, even when $s=2$, is not well understood. For instance, until now we did not know how to test whether a graph is $2\mathcal{O}$-free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that $2\mathcal{O}$-free graphs have only a polynomial number of induced paths. In this paper we prove Le's conjecture; indeed, we will show that for all $s\ge 1$, there exists $c>0$ such that every $s\mathcal{O}$-free graph $G$ has at most $|G|^c$ induced paths. This provides a poly-time algorithm to test if a graph is $s\mathcal{O}$-free, for all fixed $s$. The proof has three parts. First, there is a short and beautiful proof, due to Le, that reduces the question to proving the same thing for graphs with no cycles of length four. Second, there is a recent result of Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek, that in every $s\mathcal{O}$-free graph $G$ with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in $|G|$. And third, there is an argument that uses the result of Bonamy et al. to deduce the theorem. The last is the main content of this paper.
