اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the ErdH{o}s-Posa property for long holes in $C_4$-free graphs
334
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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].
قيم البحث
اقرأ أيضاً
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
d 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 th
e 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
ing 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.
A hole in a graph is an induced cycle of length at least $4$. Let $sge2$ and $tge2$ be integers. A graph $G$ is $(s,t)$-splittable if $V(G)$ can be partitioned into two sets $S$ and $T$ such that $chi(G[S ]) ge s$ and $chi(G[T ]) ge t$. The well-know
n ErdH{o}s-Lovasz Tihany Conjecture from 1968 states that every graph $G$ with $omega(G) < chi(G) = s + t - 1$ is $(s,t)$-splittable. This conjecture is hard, and few related results are known. However, it has been verified to be true for line graphs, quasi-line graphs, and graphs with independence number $2$. In this paper, we establish more evidence for the ErdH{o}s-Lovasz Tihany Conjecture by showing that every graph $G$ with $alpha(G)ge3$, $omega(G) < chi(G) = s + t - 1$, and no hole of length between $4$ and $2alpha(G)-1$ is $(s,t)$-splittable, where $alpha(G)$ denotes the independence number of a graph $G$.
A graph is $P_8$-free if it contains no induced subgraph isomorphic to the path $P_8$ on eight vertices. In 1995, ErdH{o}s and Gy{a}rf{a}s conjectured that every graph of minimum degree at least three contains a cycle whose length is a power of two.
In this paper, we confirm the conjecture for $P_8$-free graphs by showing that there exists a cycle of length four or eight in every $P_8$-free graph with minimum degree at least three.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
