Turán's problem and Ramsey numbers for trees

Zhi-Hong Sun ; Lin-Lin Wang ; Yi-Li Wu

Colloquium Mathematicae, Tome 139 (2015), p. 273-298 / Harvested from The Polish Digital Mathematics Library

Résumé

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V = {v₀,v₁,...,v_{n-1}}$, $E₁ = {v₀v₁,..., v₀v_{n-3},v_{n-4}v_{n-2},v_{n-3}v_{n-1}}$ and $E₂ = {v₀v₁,..., v₀v_{n-3},v_{n-3}v_{n-2},v_{n-3}v_{n-1}}$. For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r(Tₘ,Tₙ^i)$, where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

Détail

Publié le : 2015-01-01

Zbl 1312.05089

EUDML-ID : urn:eudml:doc:284134