Packing and covering immersions in 4-edge-connected graphs
Packing and covering immersions in 4-edge-connected graphs
复制标题
在 4 边连接图中封装和覆盖浸没
DOI：
10.1016/j.jctb.2021.06.005
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Liu, Chun-Hung
中科院分区：
文献类型：
--
作者：
Liu, Chun-Hung
一个图G包含另一个图H作为浸入，如果H可以从G的一个子图通过分裂边和去除孤立点而得到。本文证明了4-边连通图中关于浸入包含的Erdens-Pósa性质的一个边变式。更精确地说，我们证明了对每个图H，存在一个函数f，使得对每个4-边连通图G，要么G包含k个两两边不相交的子图，每个子图包含H作为浸入，要么G存在一组至多f（k）条边与所有这样的子图相交。这个定理在4-边连通性不能被3-边连通性取代的意义上是最好的。
A graph G contains another graph H as an immersion if H can be obtained from a subgraph of G by splitting off edges and removing isolated vertices. In this paper, we prove an edge-variant of the Erdős-Pósa property with respect to the immersion containment in 4-edge-connected graphs. More precisely, we prove that for every graph H, there exists a function f such that for every 4-edge-connected graph G, either G contains k pairwise edge-disjoint subgraphs each containing H as an immersion, or there exists a set of at most f (k) edges of G intersecting all such subgraphs. This theorem is best possible in the sense that the 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.