Half-integral ErdH{o}s-Posa property of directed odd cycles


الملخص بالإنكليزية

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.

تحميل البحث