ﻻ يوجد ملخص باللغة العربية
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)$ hitt
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, an
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
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$
For positive integers $n>dgeq k$, let $phi(n,d,k)$ denote the least integer $phi$ such that every $n$-vertex graph with at least $phi$ vertices of degree at least $d$ contains a path on $k+1$ vertices. Many years ago, ErdH{o}s, Faudree, Schelp and Si