Geodesic
Induced trees in triangle-free graphs
The electronic journal of combinatorics, Tome 15 (2008)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
We prove that every connected triangle-free graph on $n$ vertices contains an induced tree on $\exp(c\sqrt{\log n}\,)$ vertices, where $c$ is a positive constant. The best known upper bound is $(2+o(1))\sqrt n$. This partially answers questions of Erdős, Saks, and Sós and of Pultr.
DOI : 10.37236/765
Classification : 05C55, 05C05
Mots-clés : connected triangle free graph, number of vertices of an induced tree, upper bound, blow-up construction 
Jiří Matoušek; Robert Šámal. Induced trees in triangle-free graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/765
@article{10_37236_765,
     author = {Ji\v{r}{\'\i} Matou\v{s}ek and Robert \v{S}\'amal},
     title = {Induced trees in triangle-free graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/765},
     zbl = {1159.05035},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/765/}
}
TY  - JOUR
AU  - Jiří Matoušek
AU  - Robert Šámal
TI  - Induced trees in triangle-free graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/765/
DO  - 10.37236/765
ID  - 10_37236_765
ER  - 
%0 Journal Article
%A Jiří Matoušek
%A Robert Šámal
%T Induced trees in triangle-free graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/765/
%R 10.37236/765
%F 10_37236_765

Cité par Sources :