Small order graph-tree Ramsey numbers (Q1112840)

In this paper, the Ramsey number r(G,T) is determined for all, but a few exceptional cases, where G is a connected graph on five or fewer vertices and T is any tree. For a graph G, let p(G) denote the number of vertices in G, s(G) the minimum number of vertices in any color class overall \(\chi\) (G)-vertex colorings, and let \(\Delta\) (G) denote the maximum degree of a vertex of G. Let \(\epsilon (a,b)=1\) when a and b are even and 0 otherwise. Let T denote a tree and let G be any graph. Let \(t_ 1\) and \(t_ 2\) be positive integers and set \(L=t_ 1K_{p(G)-1}\cup t_ 2K_{p(G)-2}\). Choose \(t_ 1\) and \(t_ 2\) such that T is not a subgraph of \(\overline{L}\) and such that p(L) is maximal. Setting \(t(G,T)=p(L)\), we define f(G,T) to be the maximum of \((\chi (G)-1)(p(T)-1)+s(G)\), \(t(G,T)+1\), and \(\Delta (G)+\Delta (T)-\epsilon (\Delta (G),\Delta (T)).\) The main result of this paper is: Theorem 1. Let G be a connected graph with at most five vertices and let \(T_ n\) be a tree on n vertices, \(n\geq 9\). Then with but a few exceptions (those listed in (i)-(iv) below) we have \(r(G,T)=f(G,T_ n).\) (i) \(r(K_ 5-2K_ 2,K(1,n-1))=2n+1\) when n is even. (ii) \(r(K_ 5-P_ 4,K(1,n-1))=2n\) when n is even. (iii) \(r(K(2,2),T_ n)=r(K(2,3)-e,T_ n)=\max \{n+1,r(K(2,2),\Delta (T_ n))\}\) (iv) There exists a constant c such that \(n+1\leq r(K(2,3),T_ n)\leq \max \{n+c,r(K(2,3),\Delta (T_ n))\}\).