Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe edge-ErdH{o}s-Posa property
78
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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].
Let $W_t$ denote the wheel on $t+1$ vertices. We prove that for every integer $t geq 3$ there is a constant $c=c(t)$ such that for every integer $kgeq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as minor, or there is a subset $X$ of at most $c k log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$.
Let $mathbf{k} := (k_1,dots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;mathbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;mathbf{k})$ to denote the maximum of $F(G;mathbf{k})$ over all graphs $G$ on $n$ vertices. This problem was first considered by ErdH{o}s and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. We prove that, for every $mathbf{k}$ and $n$, there is a complete multipartite graph $G$ on $n$ vertices with $F(G;mathbf{k}) = F(n;mathbf{k})$. Also, for every $mathbf{k}$ we construct a finite optimisation problem whose maximum is equal to the limit of $log_2 F(n;mathbf{k})/{nchoose 2}$ as $n$ tends to infinity. Our final result is a stability theorem for complete multipartite graphs $G$, describing the asymptotic structure of such $G$ with $F(G;mathbf{k}) = F(n;mathbf{k}) cdot 2^{o(n^2)}$ in terms of solutions to the optimisation problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
