Bipartite Ramsey number for different types of trees

Abstract

For any two graphs F and H, the Ramsey number R(F, H) is the smallest positive inte ger n such that for any red-blue coloring of the edges of the complete graph Kn there is a subgraph of Kn isomorphic to F whose edges are all colored red, or a subgraph of Kn isomorphic to H whose edges are all colored blue. Let F and H now be two bipartite graphs, and s a positive integer. The s-bipartite Ramsey number bs(F, H) is the smallest positive integer t, with t ≥ s, such that for any red-blue coloring of the edges of Ks, t there is a subgraph of Ks, t isomorphic to F whose edges are all colored red, or a subgraph of Ks, t isomorphic to H whose edges are all colored blue. The case where s = t is known as the bipartite Ramsey number, denoted by b(F, H). Finally, let Tn denote a tree of order n ≥ 5 with maximum degree n − 2. In this dissertation we determine the Ramsey numbers b(K1, n, K1, m), b(K1, m, Tn), b(Tm, Tn), bs(K1,m, Tn) and bs(Tm, Tn).