Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userErdos-Posa property of minor-models with prescribed vertex sets
106
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A minor-model of a graph $H$ in a graph $G$ is a subgraph of $G$ that can be contracted to $H$. We prove that for a positive integer $ell$ and a non-empty planar graph $H$ with at least $ell-1$ connected components, there exists a function $f_{H, ell}:mathbb{N}rightarrow mathbb{R}$ satisfying the property that every graph $G$ with a family of vertex subsets $Z_1, ldots, Z_m$ contains either $k$ pairwise vertex-disjoint minor-models of $H$ each intersecting at least $ell$ sets among prescribed vertex sets, or a vertex subset of size at most $f_{H, ell}(k)$ that meets all such minor-models of $H$. This function $f_{H, ell}$ is independent with the number $m$ of given sets, and thus, our result generalizes Maders $mathcal S$-path Theorem, by applying $ell=2$ and $H$ to be the one-vertex graph. We prove that such a function $f_{H, ell}$ does not exist if $H$ consists of at most $ell-2$ connected components.
rate research
Read More
A Group Labeled Graph is a pair $(G,Lambda)$ where $G$ is an oriented graph and $Lambda$ is a mapping from the arcs of $G$ to elements of a group. A (not necessarily directed) cycle $C$ is called non-null if for any cyclic ordering of the arcs in $C$, the group element obtained by `adding the labels on forward arcs and `subtracting the labels on reverse arcs is not the identity element of the group. Non-null cycles in group labeled graphs generalize several well-known graph structures, including odd cycles. In this paper, we prove that non-null cycles on Group Labeled Graphs have the half-integral Erdos-Posa property. That is, there is a function $f:{mathbb N}to {mathbb N}$ such that for any $kin {mathbb N}$, any group labeled graph $(G,Lambda)$ has a set of $k$ non-null cycles such that each vertex of $G$ appears in at most two of these cycles or there is a set of at most $f(k)$ vertices that intersects every non-null cycle. Since it is known that non-null cycles do not have the integeral Erdos-Posa property in general, a half-integral Erdos-Posa result is the best one could hope for.
Robertson and Seymour proved that the family of all graphs containing a fixed graph $H$ as a minor has the ErdH{o}s-Posa property if and only if $H$ is planar. We show that this is no longer true for the edge version of the ErdH{o}s-Posa property, and indeed even fails when $H$ is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos.
A chordless cycle, or equivalently a hole, in a graph $G$ is an induced subgraph of $G$ which is a cycle of length at least $4$. We prove that the ErdH{o}s-Posa property holds for chordless cycles, which resolves the major open question concerning the ErdH{o}s-Posa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either $k+1$ vertex-disjoint chordless cycles, or $c_1k^2 log k+c_2$ vertices hitting every chordless cycle for some constants $c_1$ and $c_2$. It immediately implies an approximation algorithm of factor $mathcal{O}(sf{opt}log {sf opt})$ for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least $ell$ for any fixed $ellge 5$ do not have the ErdH{o}s-Posa property.
We prove that there exists a function $f:mathbb{N}rightarrow mathbb{R}$ such that every digraph $G$ contains either $k$ directed odd cycles where every vertex of $G$ is contained in at most two of them, or a vertex set $X$ of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral ErdH{o}s-Posa property of undirected odd cycles, proved by Reed [Mangoes and blueberries. Combinatorica 1999], to digraphs.
We prove that there exists a function $f(k)=mathcal{O}(k^2 log k)$ such that for every $C_4$-free graph $G$ and every $k in mathbb{N}$, $G$ either contains $k$ vertex-disjoint holes of length at least $6$, or a set $X$ of at most $f(k)$ vertices such that $G-X$ has no hole of length at least $6$. This answers a question of Kim and Kwon [ErdH{o}s-Posa property of chordless cycles and its applications. JCTB 2020].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
