Zobrazeno 1 - 3
of 3
pro vyhledávání: '"Guido Besomi"'
Publikováno v:
Combinatorics, Probability and Computing. 30:741-761
We prove the Erdős–Sós conjecture for trees with bounded maximum degree and large dense host graphs. As a corollary, we obtain an upper bound on the multicolour Ramsey number of large trees whose maximum degree is bounded by a constant.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ce38d0a49056686eff132251f2b61c92
https://doi.org/10.1017/s0963548320000528
https://doi.org/10.1017/s0963548320000528
Publikováno v:
SIAM Journal on Discrete Mathematics. 34:2108-2123
We propose the following conjecture: For every fixed $\alpha\in [0,\frac 13)$, each graph of minimum degree at least $(1+\alpha)\frac k2$ and maximum degree at least $2(1-\alpha)k$ contains each tree with $k$ edges as a subgraph. Our main result is a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::264f9ad3d6d2995e37b52a8421cda01c
https://doi.org/10.1137/19m1277667
https://doi.org/10.1137/19m1277667
We conjecture that every $n$-vertex graph of minimum degree at least $\frac k2$ and maximum degree at least $2k$ contains all trees with $k$ edges as subgraphs. We prove an approximate version of this conjecture for trees of bounded degree and dense
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c5aec9db01bc8826e4ee01f099762b50
