اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGraphs with no induced house nor induced hole have the de Bruijn-ErdH{o}s property
88
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A set of n points in the plane which are not all collinear defines at least n distinct lines. Chen and Chvatal conjectured in 2008 that a similar result can be achieved in the broader context of finite metric spaces. This conjecture remains open even for graph metrics. In this article we prove that graphs with no induced house nor induced cycle of length at least~5 verify the desired property. We focus on lines generated by vertices at distance at most 2, define a new notion of ``good pairs that might have application in larger families, and finally use a discharging technique to count lines in irreducible graphs.
قيم البحث
اقرأ أيضاً
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$.
We prove that for every integer $k$, there exists $varepsilon > 0$ such that for every n-vertex graph $G$ with no pivot-minor isomorphic to $C_k$, there exist disjoint sets $A,B subseteq V(G)$ such that $|A|,|B| geq varepsilon n$, and $A$ is either c
omplete or anticomplete to $B$. This proves the analog of the ErdH{o}s-Hajnal conjecture for the class of graphs with no pivot-minor isomorphic to $C_k$.
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 homogeneous set of a graph $G$ is a set $X$ of vertices such that $2le lvert Xrvert <lvert V(G)rvert$ and no vertex in $V(G)-X$ has both a neighbor and a non-neighbor in $X$. A graph is prime if it has no homogeneous set. We present an algorithm
to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs.
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].
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
