Turán's problem and Ramsey numbers for trees
Volume 139 / 2015
Colloquium Mathematicum 139 (2015), 273-298
MSC: 05C55, 05C35, 05C05.
DOI: 10.4064/cm139-2-8
Abstract
Let $T_n^1=(V,E_1)$ and $T_n^2=(V,E_2)$ be the trees on $n$ vertices with $V=\{v_0,v_1,\ldots ,v_{n-1}\}$, $E_1=\{v_0v_1,\ldots ,v_0v_{n-3},v_{n-4}v_{n-2},v_{n-3}v_{n-1}\}$ and $E_2=\{v_0v_1,\ldots ,$ $v_0v_{n-3},v_{n-3}v_{n-2}, v_{n-3} v_{n-1}\}$. For $p\ge n\ge 5$ we obtain explicit formulas for ${\rm ex}(p;T_n^1)$ and ${\rm ex}(p;T_n^2)$, where ${\rm ex}(p;L)$ denotes the maximal number of edges in a graph of order $p$ not containing $L$ as a subgraph. Let $r(G_ 1, G_ 2)$ be the Ramsey number of the two graphs $G_1$ and $G_2$. We also obtain some explicit formulas for $r(T_m,T_n^i)$, where $i\in \{1,2\}$ and $T_m$ is a tree on $m$ vertices with $\varDelta (T_m)\le m-3$.
