Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraphs with no induced house nor induced hole have the de Bruijn-ErdH{o}s property
88
0
0.0
(
0
)
Added by
Laurent Beaudou
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 complete 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, 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.
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].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
