Classes of graphs that exclude a tree and a clique and are not vertex Ramsey

A class Γ of graphs is vertex Ramsey if for all H ∈ Γ there exists G ∈ Γ such that for all partitions of the vertices of G into two parts, one of the parts contains an induced copy of H. Forb (T,K) is the class of graphs that induce neither T nor K. Let T(k,r) be the tree with radius r such that each nonleaf is adjacent to k vertices farther from the root than itself. Gyárfás conjectured that for all trees T and cliques K, there exists an integer b such that for all G in Forb (T,K), the chromatic number of G is at most b. Gyárfás' conjecture implies a weaker conjecture of Sauer that for all trees T and cliques K, Forb (T,K) is not vertex Ramsey. We use techniques developed for attacking Gyárfás' conjecture to prove that for all q, r and sufficiently large k, Forb (T(k,r),K_q) is not vertex Ramsey.