Induced paths in graphs without anticomplete cycles
Induced paths in graphs without anticomplete cycles
复制标题
图中没有反完全循环的诱导路径
DOI：
10.1016/j.jctb.2023.10.003
复制
发表时间：
2024
期刊：
影响因子：
--
通讯作者：
Nguyen T
中科院分区：
文献类型：
--
作者：
Nguyen T
设一个图是Os-free的，其中s≥ 1是一个整数，如果不存在图的s个圈是两两点不相交的，并且没有边连接它们。这样的图的结构，即使当s= 2时，也不是很好理解。例如，到目前为止，我们还不知道如何在多项式时间内测试一个图是否是无O2的;并且由于Ngoc Khang Le，有一个开放的猜想，即无O2的图只有多项式数量的诱导路径。本文证明了Le的猜想，证明了对所有s≥ 1，存在c> 0使得每个Os-free图G至多有|G| c诱导路径，其中|G|是顶点数。这提供了一个多时间算法来测试一个图是否是O s-自由的，对于所有固定的s。证明有三个部分。首先，有一个简短而美丽的证明，由于Le，它将问题简化为证明没有长度为4的圈的图。第二，Bonamy，Bonnet，Déprés，Esperet，Geniet，Hilaire，Gesassé和Wesolek最近的一个结果是，在每个没有长为4的圈的O s-free图G中，存在一个与每个圈相交的顶点集，其大小在|G|.第三，有一个论点，使用Bonamy等人的结果来推导定理。最后是本文的主要内容。
Let us say a graph is O s-free, where s≥ 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 O 2-free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that O 2-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≥ 1, there exists c> 0 such that every O s-free graph G has at most| G| c induced paths, where| G| is the number of vertices. This provides a poly-time algorithm to test if a graph is O s-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 O s-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.
具有有界诱导循环堆积数的稀疏图具有对数树宽
DOI：
--
发表时间：
2022
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Marthe Bonamy;Édouard Bonnet;Hugues Déprés;Louis Esperet;Colin Geniet;Claire Hilaire;Stéphan Thomassé;Alexandra Wesolek
通讯作者：
Alexandra Wesolek
影响因子：
1.1
作者：
Kaminski, Marcin;Medvedev, Paul;Milanic, Martin
通讯作者：
Milanic, Martin