UNIVERSITY OF THE WITWATERSRAND MASTER’S DISSERTATION Bipartite Ramsey Number for Different Types of Trees Student: Mr. Lesego R. E. Mabusela (1043480) Supervisor: Mr. Ronald J. Maartens Co-Supervisor: Prof. Elizabeth Jonck A Master’s dissertation submitted to the Faculty of Science in fulfillment of the requirements for the degree of Master‘s of Science in Mathematics in the School of Mathematics May 4, 2022 http://www.university.com http://www.johnsmith.com http://www.jamessmith.com http://www.jamessmith.com http://department.university.com i Declaration of Authorship I, Lesego Mabusela, student number 1043480, declare that this dissertation titled “Bipartite Ramsey Number for Different Types of Trees” and the work presented in it are my own. I confirm that: • This work was done wholly or mainly while in candidature for a masters de- gree at this University. • Where any part of this dissertation has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated. • Where I have consulted the published work of others, this is always clearly attributed. • Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work. • I have acknowledged all main sources of help. • Where the dissertation is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself. Signed: Date: ii UNIVERSITY OF THE WITWATERSRAND Abstract Faculty of Science School of Mathematics Master‘s of Science in Mathematics Bipartite Ramsey Number for Different Types of Trees by Ronald J. Maartens, Elizabeth Jonck and Lesego Mabusela. 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). HTTP://WWW.UNIVERSITY.COM http://faculty.university.com http://department.university.com iii Acknowledgements I would like to express my deep and sincere gratitude to my research supervisors Mr. Ronald J. Maartens and Prof. Elizabeth Jonck for providing me with an oppor- tunity to carry out my research under their invaluable guidance and patience. Their sincerity and motivation kept me inspired throughout my research. They taught me the methodology to carry out this research and present it in the best way possible. Their background knowledge in this area as well as their assistance in the different phases of this dissertation have been of great help and are much appreciated. iv Contents Declaration of Authorship i Abstract ii Acknowledgements iii 1 Introduction 1 1.1 Main Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Basic Definitions and Terminology . . . . . . . . . . . . . . . . . . . . . 1 1.3 Ramsey Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 The Ramsey Number for Two Trees 14 2.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 The Ramsey Number for Two Stars K1, 2 and K1, m . . . . . . . . . . . . 14 2.3 The Ramsey Number for Two Stars K1, n and K1, m . . . . . . . . . . . . 18 2.4 The Ramsey Number for a Star K1, m and a Tree T′n . . . . . . . . . . . . 26 2.5 The Ramsey Number for Two Trees . . . . . . . . . . . . . . . . . . . . . 32 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3 The k-Ramsey Number for Two Stars 43 3.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2 The 2-Ramsey Number for Two Stars K1, 2 and K1, m . . . . . . . . . . . 43 3.3 The k-Ramsey Number for Two Stars K1, n and K1, m . . . . . . . . . . . 46 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4 The Bipartite Ramsey Number for Two Trees 66 4.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2 The Bipartite Ramsey Number for Two Stars K1, 2 and K1, m . . . . . . . 66 v 4.3 The Bipartite Ramsey Number for Two Stars K1, n and K1, m . . . . . . . 68 4.4 The Bipartite Ramsey Number for a Star K1, m and a Tree T′n . . . . . . . 73 4.5 The Bipartite Ramsey Number for Two Trees . . . . . . . . . . . . . . . 77 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5 The s-Bipartite Ramsey Number for Two Trees 81 5.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 The s-Bipartite Ramsey Number for Two Stars K1, n and K1, m . . . . . 81 5.3 The s-Bipartite Ramsey Number for a Star K1, m and a Tree T′n . . . . . . 84 5.4 The s-Bipartite Ramsey Number for Two Trees T′m and T′n . . . . . . . . 89 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6 Closing Chapter 95 Bibliography 98 vi List of Figures • Figure 1.2.1: A simple graph G. • Figure 1.2.2: Spanning subgraph H of G. • Figure 1.2.3: A z− w path of order four and size three. • Figure 1.2.4: A cycle of order four. • Figure 1.2.5: Complete graph K4. • Figure 1.2.6: The complete bipartite graph K3,3. • Figure 1.2.7: A star K1,6. • Figure 1.2.8: A tree T′5. • Figure 1.2.9: A red-blue coloring of edges of K5. • Figure 1.2.10: A Hamiltonian graph. • Figure 1.2.11: A perfect matching. • Figure 1.2.12: A 2-factor graph. • Figure 1.3.1: A red-blue coloring of edges of K3. • Figure 2.2.1: A red-blue edge coloring of the complete graph of order two. • Figure 2.2.2: A red-blue edge coloring of K3. • Figure 2.2.3: A red-blue coloring of edges of the complete graph Km + 1. • Figure 3.2.1: A red-blue edge coloring of H. • Figure 4.2.1: A red-blue coloring of edges of K1,1. vii • Figure 4.4.1: A complete bipartite graph H. • Figure 4.4.2: A red-blue coloring of edges of H. • Figure 5.3.1: A complete bipartite graph H. • Figure 5.3.2: A red-blue coloring of edges of H. viii List of Tables • Table 2.2.1: The number of red and blue edges incident to v in Km + 2. • Table 2.3.1: The number of red and blue edges incident to v in Kn + m. • Table 2.3.2: The number of red and blue edges incident to v in Kn + m. • Table 2.4.1: The number of red and blue edges incident to v inKn + m− 2. • Table 2.5.1: The number of red and blue edges incident to v in Kn + m− 4. • Table 3.2.1: The number of red and blue edges incident to u in K2m + 1. • Table 3.3.1: The number of red and blue edges incident to v in K(k− 1)q, q + 1. • Table 4.2.1: The number of red and blue edges incident to u in Km + 1, m + 1. • Table 4.3.1: The number of red and blue edges incident to u in Kn + m− 1, n + m− 1. • Table 4.3.2: The number of red and blue edges incident to v in Kq, q + 1. • Table 4.4.1: The number of red and blue edges incident to v in Kn + m− 3, n + m− 3. • Table 4.5.1: The number of red and blue edges incident to v in Kn + m− 5, n + m− 5. • Table 5.2.1: The number of red and blue edges incident to v in Ks, t. • Table 5.3.1: The number of red and blue edges incident to v in Ks, t. • Table 5.3.2: The number of red and blue edges incident to v in Kn + m− 3, n + m− 3. • Table 5.4.1: The number of red and blue edges incident to v in Ks, t. • Table 5.4.2: The number of red and blue edges incident to v in Kn + m− 5, n + m− 5. 1 Chapter 1 Introduction 1.1 Main Research Questions In this dissertation our main research questions are: • What is the bipartite Ramsey number of two trees with various structures? • What is the s-bipartite Ramsey number of two trees with various structures? 1.2 Basic Definitions and Terminology We give some basic Graph Theory definitions in this section. The reader is referred to the textbook Graphs and Digraphs by Chartrand, Lesniak and Zhang [1] for any unde- fined terms and concepts in Graph Theory. We advise the reader that we use colored diagrams in this dissertation to better visualise concepts. A graph G is a finite nonempty set V of objects called vertices (singular called vertex) together with a (possibly empty) set E of 2-element subsets of V called edges. In this dissertation we only consider finite simple graphs which are graphs with no loops or multiple edges between the same two vertices, unless otherwise stated. A loop is defined to be an edge which connects a vertex to itself. We consider graphs that are undirected which are graphs with edges that have no direction attached to them. The number of vertices in the graph G is called the order of G and the number of edges is called the size of G, that is, the cardinality of the vertex set and the edge set respectively. In Figure 1.2.1 the graph G has order six and size seven. Chapter 1. Introduction 2 To explicitly show that a graph G has vertex set V and edge set E it is sometimes denoted by G = (V, E). To stress that V is the vertex set of G we write V as V(G) and for a similar explanation we write the edge set E as E(G). Figure 1.2.1: A simple graph G. z u v w yx If uv is an edge of G, then vertices u and v are said to be adjacent to each other. Two adjacent vertices are called neighbours of each other. If v is a vertex and uv is an edge, then v and uv are said to be incident to each other. The degree of a vertex v in the graph G is the number of vertices in G that are adjacent to v. Equivalently the degree of vertex v is the number of edges incident to v. In this dissertation the degree of a vertex v is denoted by degG v or, more simply, by deg v if the graph G under consideration is clear. In graph G of Figure 1.1 we have that deg v = 3 and deg w = 2. ∆(G) denotes the maximum degree of G which is defined as the largest degree among the vertices of G . Similarly, the minimum degree of G is denoted by δ(G). In Figure 1.2.1 graph G has ∆(G) = 3 and δ(G) = 1. Two graphs that have the exact same structure are said to be isomorphic. If G and H are isomorphic, then there exists a bijective function φ : V(G) → V(H) such that any two vertices u and v are adjacent in G if and only if φ(u) and φ(v) are adjacent in H. Isomorphic graphs G and H have the same number of vertices, same number of edges and the degree of the vertices in G is the same as the degree of the corre- sponding vertices in H. A graph H is said to be a subgraph of a graph G if V(H) ⊆ V(G) and E(H) ⊆ E(G). If V(H) = V(G) and E(H) ⊆ E(G), then H is called a spanning subgraph of G. The Chapter 1. Introduction 3 graph in Figure 1.2.2 is the spanning subgraph H of graph G given in Figure 1.2.1. We see in Figure 1.2.1 and Figure 1.2.2 that G and H have the same number of ver- tices but graph H has less edges than graph G. Figure 1.2.2: Spanning subgraph H of G. z u v w yx For any two vertices u and v, not necessarily distinct, a u− v walk in G is a sequence of vertices and edges in G, beginning at u and ending at v. In a walk we repeat edges and vertices. A walk whose initial and terminal vertices are distinct is called an open walk, otherwise it is called a closed walk. A u− v open walk with no repeated edges and vertices is called a path. A path of order m is denoted by Pm. The graph in Figure 1.2.3 gives the graph of P4. Figure 1.2.3: A z− w path of order four and size three. z u v w A u− v closed walk with no repeated edges and no repeated vertices apart from the initial vertex and terminal vertex is called a cycle. A cycle of order m is denoted by Cm where m ≥ 3. The graph in Figure 1.2.4 is the graph of C4. Figure 1.2.4: A cycle of order four. u v yx A graph is said to be complete if every two distinct vertices of the n vertices in the graph are adjacent to each other and is denoted by Kn. Therefore, Kn is a graph of Chapter 1. Introduction 4 order n and size ( n 2 ) = n(n− 1) 2 . The graph in Figure 1.2.5 gives an example of K4. A trivial graph is a graph of order one and a nontrivial graph is a graph with two or more vertices. A graph of size zero is called an empty graph and so a nonempty graph has one or more edges. Figure 1.2.5: Complete graph K4. If all the vertices of a graph G have the same degree, then G is called a regular graph. That is, if every vertex of G has degree r, then we say that G is r-regular. Note that if we only consider a cycle graph, then every vertex on the cycle has degree two and thus the cycle graph is 2− regular. A nontrivial graph G is a complete bipartite graph if it is possible to partition V(G) into two subsets U and W, called partite sets, such that every vertex in U is a neigh- bour of a vertex in W with no edge between any two vertices in the same partite set. More generally, a graph G is a k-partite graph if it is possible to partition V(G) into k partite sets, say V1, V2, · · · , Vk, such that no vertices in the same partite set are adjacent. A graph G is said to be balanced if the number of vertices between any two partite sets in G differ by at most one. Figure 1.2.6: The complete bipartite graph K3,3. A k-partite graph having partite sets V1, V2, · · · , Vk is called a complete k-partite graph if all of the vertices in Vi are adjacent to all of the vertices in Vj, this is when Chapter 1. Introduction 5 1 ≤ i, j ≤ k for i 6= j. The complete bipartite graph is denoted by Kn, m if it has two partites U and W, where U has n vertices and W has m vertices. In Figure 1.2.6 we have an example of the complete bipartite graph K3,3. A special case of the complete bipartite graphs is the graph K1,n which we call a star. The graph in Figure 1.2.7 gives an example of a K1,6. A tree is a connected graph without cycles, and a tree on n vertices is denoted by Tn. Stars and paths are all special types of trees. Figure 1.2.7: A star K1,6 We use T′n to denote the tree of order n ≥ 5 whose maximum degree is n − 2. We highlight that T′n is not a star since the maximum degree of T′n is n− 2. The graph in Figure 1.2.8 is a tree T′5. Figure 1.2.8: A tree T′5. For the tree T′n we consider n ≥ 5 because • if n = 4, then the maximum degree of T′4 is 4− 2 = 2 implying that T′4 is isomorphic to P4, Chapter 1. Introduction 6 • if n = 3, then the maximum degree of T′3 is 3− 2 = 1 implying that T′3 a disconnected graph and we are only considering connected graphs, • if n = 2, then T′2 is an empty graph since the maximum degree is zero and we are done, and • if n = 1, then the graph T′1 does not exist as it has a negative maximum degree. There are numerous ways of producing a new graph from at least one graph. The complement G of a graph G is a graph whose vertex set is V(G) and where uv is an edge in G if and only if uv is not an edge in graph G. Obviously the empty graph is the complement of the complete graph. The coloring of edges is a process where a color from a group of possible colors is assigned to every edge given in a graph. In this dissertation we only assign one color to an edge and we only make use of two colors, namely red and blue. Since an edge is assigned either a red color or a blue color, we have that in the com- plete graph all of the edges colored red form a subgraph which we denote by GR and all of the edges colored blue form a subgraph which we denote by GB. Note that the two subgraphs GR and GB are complementary graphs of each other. The graph in Figure 1.2.9 gives an example of this. Figure 1.2.9: A red-blue coloring of edges of K5. Chapter 1. Introduction 7 We mostly make use of the complements when we talk of the red-blue coloring of edges of the graph G since all the edges that are not colored blue in G is colored red producing a red subgraph of G. Let G be a graph. A Hamiltonian path of graph G is a path in G that contains every vertex of G, while a cycle in G that contains every vertex of G is called a Hamiltonian cycle. Figure 1.2.10 gives an example of a graph containing a Hamiltonian cycle. A graph that contains a Hamiltonian cycle is in short called Hamiltonian. Necessarily, the order of a Hamiltonian graph is at least three and every Hamiltonian graph con- tains a Hamiltonian path. However, a graph with a Hamiltonian path need not be Hamiltonian. Figure 1.2.10: A Hamiltonian graph. The following results helps us later on in determining whether a graph is Hamilto- nian or not. Theorem 1.2.1. [2] All graphs G of order n ≥ 3 with minimum degree δ(G) ≥ n/2 are Hamiltonian. Theorem 1.2.2. [2] If G is the balanced complete k-partite graph with k ≥ 3, then G is Hamiltonian. In a graph G, a set M of edges, with no two edges incident to the same vertex, is called a matching. A matching M in G is a perfect matching if every vertex of G is incident with some edge in M. If M is a perfect matching in G, then G has order n = 2k for some positive integer k where |M| = k. Thus, only graphs of even order have a perfect matching. The graph in Figure 1.2.11 gives an example of a perfect matching when n = 8. Chapter 1. Introduction 8 Figure 1.2.11: A Perfect Matching. We also refer to factors of a graph G. A factor of a graph G simply means a spanning regular subgraph of G. A spanning k-regular subgraph of G is called a k − f actor. The edges of the graph are partitioned into disjoint k-factors. The disjoint union of a graph is an operation that combines two or more graphs to from a larger graph. Figure 1.2.12 gives us an example of a 2-factor graph. The edge set of a 1-factor in a graph G is a perfect matching in G. Figure 1.2.12: A 2-factor graph. The following results are needed for our results later on. Theorem 1.2.3. [3], [4] The complete graph K2n is 1-factorable. Theorem 1.2.4. [5] A graph G is 2-factorable if and only if G is 2p regular, where p is a positive integer. Theorem 1.2.5. [6] For every positive integer n the graph Kn, n is 1-factorable. The notation n | a means that a is divisible by n. In mathematics, divisibility means that a number divides evenly into another number or itself with no remainder. For example two divides evenly into eight and so we write 2 | 8. However, three would leave us with a remainder when we divide eight by three so we write 3 - 8 to denote that eight is not divisible by three. Modulo is a mathematics operation that finds the remainder when one integer is Chapter 1. Introduction 9 divided by another. Modulo is often represented with mod. For integer a, b and r, if a is the dividend, b the divisor and r the remainder we write a (mod b) ≡ r. 1.3 Ramsey Theory Ramsey Theory is named after the British Mathematician Frank Plumpton Ramsey (1903 - 1930). Frank was the first to mention a lemma on what is named today as Ramsey’s Theorem in his second paper On a problem of formal logic [7] in 1930. Ramsey Theory is a branch in mathematics that focuses on the appearance of order in a structure given a substructure of a particular property. Ramsey Theory mostly answers the question: "How many vertices in a structure is needed to ensure that a particular substructure of some given property is contained in that structure?". Ramsey Theory has many interesting applications and often quickly become com- plicated especially if we consider very large structures. We focus on a few variations of the original Ramsey number in this dissertation. Each following chapter in this dissertation focus on a particular type of Ramsey number for two trees. In Chapter 2 we begin by confirming the Ramsey number for each pair K1, n and K1, m of stars of order n + 1 ≥ 3 and m + 1 ≥ 3 respectively. This result was first mentioned by S. Burr and J. Roberts in their article On the Ramsey numbers for stars [8] in 1973, their version of a Ramsey number was as follows. Given any two graphs F and H, the Ramsey number R(F, H) is defined to be the small- est positive integer n such that for any red-blue coloring of the edges of the complete graph of order n, Kn, there is either 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. If R(F, H) = n in the definition of the Ramsey numbers of two graphs F and H, Chapter 1. Introduction 10 then for every red-blue coloring of the edges of the complete graph Kn there exist either a red F or a blue H. Also, we have that there exists a red-blue coloring of edges of the complete graph Kn− 1 where there is neither a red F nor a blue H. We emphasize that in a complete graphs where the red subgraph is the comple- ment of the blue subgraph and vice versa. The graph in Figure 1.3.1 illustrates this statement again. In Figure 1.3.1 we first have a K3 with no edge coloring and then we assign a red-blue edge coloring in the graphs below the K3 with no edge coloring. We see that the red subgraph is the complement of the blue subgraph and vice versa. Figure 1.3.1: A red-blue coloring of edges of K3. In Section 2.4 we prove the Ramsey number for a star of order m ≥ 2 and a tree T′n of order n ≥ 5 whose maximum degree is n− 2. We prove the Ramsey number for two trees T′m and T′n where m ≥ 5 and n ≥ 5 in Section 2.5. The Ramsey numbers R(K1, m, T′n) and R(T′m, T′n) was studied by Guo and Volkmann in their article Tree Ramsey numbers [9] in 1995. We then analyse the k-Ramsey number for each pair K1, n and K1, m of stars of or- der n + 1 and m + 1 respectively, where n ≥ 2 and m ≥ 2 in Chapter 3. Andrews, Chartrand, Lumduanhom and Zhang introduced the concept of k-Ramsey numbers in their article Stars and Their k-Ramsey numbers [10] in 2017. Their version of a Ram- sey number is as follows. Chapter 1. Introduction 11 For any two graphs F and H, and an integer k with 2 ≤ k < R(F, H), the k-Ramsey number Rk(F, H) is the smallest positive order of the balanced complete k-partite graph G such that for any red-blue coloring of the edges of G results in a subgraph of G isomorphic to F whose edges are all colored red, or a subgraph of G isomorphic to H whose edges are all colored blue. The authors of Stars and Their k-Ramsey numbers [10] presented a formula for the k-Ramsey number of any two stars K1, n and K1, m of order n + 1 ≥ 3 and m + 1 ≥ 3 respectively. They also considered the k-Ramsey number for two cycles of order four in the article. We stress that k is defined strictly between two and the Ramsey number R(F, H). Since if k = 1, then the graph considered is an empty graph as all the vertices are in one partite set and if k = R(F, H), then the graph considered has one vertex in each partite set, resulting in the balanced complete k-partite graph to be a complete graph of order k and so Rk(F, H)= R(F, H). The goal of Chapter 4 is to present a formula for the bipartite Ramsey number of two trees. We begin by determining the bipartite Ramsey number for the pair of stars K1, n and K1, m of order n + 1 ≥ 3 and m + 1 ≥ 3 in Section 4.3. We use the fol- lowing lemma from the article Another view on bipartite Ramsey numbers [11] to assist us in estimating the bipartite Ramsey number from Corollary 3.3.1 in Chapter 3. Lemma 1. If F and H are bipartite graphs, then R2(F, H) is either 2b(F, H) or 2b(F, H)− 1. The conditions for R2(F, H) = 2b(F, H) or R2(F, H) = 2b(F, H)− 1 is still unknown. In Section 4.4 we investigate the bipartite Ramsey number for a star of order n ≥ 2 and a tree T′n of order n ≥ 5 whose maximum degree is n− 2. Christou, Iliopoulos and Miller studied the bipartite Ramsey number of simple graphs such as trees in their article Bipartite Ramsey numbers involving stars, stripes and trees [12] in 2013. We Chapter 1. Introduction 12 furthermore investigate the biparite Ramsey number for two trees T′m and T′n of or- der m, n ≥ 5 in Section 4.5 In 1998, Hattingh and Henning introduced the concept of bipartite Ramsey num- bers in their article Star-path bipartite Ramsey number [13]. Their version of a bipartite Ramsey number is as follows. For bipartite graphs F and H, the bipartite Ramsey number b(F, H) is the smallest posi- tive integer n such that for any red-blue coloring of edges of the complete bipartite graph Kn, n there is either a subgraph of Kn, n isomorphic to F whose edges are all colored red or a subgraph of Kn, n isomorphic to H whose edges are all colored blue. In the article Star-path bipartite Ramsey number [13] the authors also considered the multicoloring of edges but we only consider a two edge coloring in this dissertation. The authors of Star-path bipartite Ramsey number [13] established the number b(Pm, K1, n) for all integers n, m ≥ 2, where Pm denotes a path of order m and K1, n a star of order n + 1 ≥ 3. In our dissertation we focus on the bipartite Ramsey number b(K1, n, K1, m) for the pair K1, n and K1, m of stars of order n + 1 ≥ 3 and m + 1 ≥ 3 respectively. In our study of bipartite Ramsey numbers for two stars that we only find the number b(K1, n, K1, m) when the number of vertices is divisible by the number of partite sets. When the number of vertices is not divisible by the number of partite sets, then k is defined between three and R(K1, n, K1, m). From our definition of the bipartite Ramsey number, if b(F, H) = b for bipartite graphs F and H, then there exist a complete bipartite graph Kb, b such that for every red-blue edge coloring of Kb, b there is either a red F or a blue H. That is there ex- ists a red-blue edge coloring of the complete graph Kb− 1, b− 1 where there is neither a red F nor a blue H. We have used the formula we established in Corollary 3.3.1 of Chapter 3 to estimate the bipartite Ramsey results by also using the result from Lemma 1. The case where both F and H are stars is proved in Chapter 4. Chapter 1. Introduction 13 The main goal of Chapter 5 is to present the formula for the s-bipartite Ramsey num- ber for the pair of bipartite graphs F and H. We begin by first proving the s-bipartite Ramsey number for the pair of stars K1, n and K1, m of size n ≥ 2 and m ≥ 2, respectively, which was studied by Olejniczak in his PhD dissertation Variations in Ramsey Theory [14] in 2019. We then investigate the s-bipartite Ramsey number for a star K1, m of order m + 1 ≥ 3 and a tree T′n of order n ≥ 5 in Section 5.3, followed by the s-bipartite Ramsey number for two trees T′m and T′n of order m, n ≥ 5. In Chapter 3 we focus on the number Rk(K1, n, K1, m) of the balanced complete k- partite graphs. A graph is said to be balanced if the number of vertices in any of the two partite sets differ by at most one. In Chapter 5 we determine the formula of the s-bipartite Ramsey number for the pair of bipartite graphs F and H of the complete bipartite graph which is not necessarilly balanced. Bi, Chartrand and Zhang first mentioned the concept of s-bipartite Ramsey num- bers in their article Another view of bipartite Ramsey numbers [11] in 2018. This version of the Ramsey number is as follows: For bipartite graphs F and H, and a positive integer s, the s-bipartite Ramsey number bs(F, H) is the smallest positive integer t, with t ≥ s, such that for any red-blue edge coloring of Ks, t results in a red F or a blue H. In the article Another view of bipartite Ramsey numbers [11] the authors only considered the s-bipartite Ramsey number of two 4-cycles and some complete bipartite graphs. We aim to further their study by finding the full results of the number bs(K1, m, T′n) and the number bs(T′n, T′m). 14 Chapter 2 The Ramsey Number for Two Trees 2.1 Purpose The purpose of this chapter is to prove the general formula for the Ramsey number of two trees F and H. For purposes of our dissertation, the trees we consider are stars and trees T′n on n ≥ 5 vertices with ∆(T′n) = n− 2. 2.2 The Ramsey Number for Two Stars K1, 2 and K1, m In this section we look at R(K1, 2, K1, m) where m ≥ 2. For the sake of completeness we give the Ramsey result of two stars K1, 1 and K1, 1. We notice that the star K1, 1 is isomorphic to the path P2. It is trivial from Figure 2.2.1 that in every red-blue coloring of the edges of K2 we always either have a red K1, 1 or a blue K1, 1. In the article On Ramsey-type problems [15] we have that R(P2, P2) = 2 and consequently we have that R(K1, 1, K1, 1) = 2. Otherwise, we either have an empty graph or multiple copies of K1, 1. Figure 2.2.1: A red-blue edge coloring of the complete graph of order two. We also have it necessary to show that R(K1, 2, K1, 2)= 3. Notice that K1, 2 is isomor- phic to P3. In Figure 2.2.2 we have that in every red-blue coloring of the edges of K3 there is always either a red K1, 2 or a blue K1, 2. Chapter 2. The Ramsey Number for Two Trees 15 Figure 2.2.2: A red-blue edge coloring of K3. We see in Figure 2.2.1 that there is a red-blue coloring of the edges of K2 where there is neither a red K1, 2 nor a blue K1, 2. Therefore we have R(K1, 2, K1, 2)= 3. In order to determine R(K1, 2, K1, m) where m ≥ 2, we reflect consideration on two cases according to the parity of m. The statement of the theorem below was given by Burr and Roberts in 1973 in their article On the Ramsey number of stars [8]. The proof is original and not from the paper. Theorem 2.2.1. For m ≥ 2, R(K1, 2, K1, m) =  m + 1 if m is even, m + 2 if m is odd. Proof We reflect consideration on two cases as indicated by whether m is even or m is odd. Case 1: m is odd. We first show that R(K1, 2, K1,m) ≤ m + 2. Let G = Km + 2 be the complete graph of order m + 2. Then every vertex v of G has degree m + 1. Also, consider a red-blue coloring of the edges of the complete graph G resulting in a red subgraph GR of G and a blue subgraph GB of G. Assume that there is neither a red K1, m nor a blue K1, 2. Let v be any arbitrary vertex of the complete graph G. In Table 2.2.1 we give all of the different ways to choose red and blue edges incident to vertex v which has degree m + 1 in G. We see that if degGR v ≥ m, then G always has a red K1, m, and if degGB v ≥ 2, then G always has a blue K1, 2 as indicated in the last column. Chapter 2. The Ramsey Number for Two Trees 16 Table 2.2.1: The number of red and blue edges incident to v in Km + 2. degGR v degGB v Contradiction m + 1 0 red K1, m m 1 red K1, m m− 1 2 blue K1, 2 m− 2 3 blue K1, 2 ... ... ... 2 m− 1 blue K1, 2 1 m blue K1, 2 0 m + 1 blue K1, 2 As a result we have that there is always either a blue K1, 2 or a red K1, m in every red-blue coloring of the edges of the complete graph G. Therefore, we have R(K1,2, K1,m) ≤ m + 2. We now show that R(K1, 2, K1, m) > m + 1. Let H be a complete graph of order m + 1. Since m is odd, m + 1 is even. Let v be an arbitrary vertex of H. Let C be a cycle that passes through the vertices of H exactly once. We have that C is a Hamiltonian cycle in H by Theorem 1.2.1. Let F = H − E(C). Then F is a regular graph of degree m− 2. Reflect into consideration the red-blue coloring of the edges of H. Color the edges of graph F red and alternate the colors red and blue on the edges of C in the complete graph H. Then the blue subgraph HB of H is 1-regular and the red subgraph HR of H is (m− 1)-regular. As a result, we have that there is a red-blue coloring of the edges of the complete graph G where there is neither a blue K1, 2 nor a red K1, m. Therefore we conclude that R(K1, 2, K1, m) > m + 1 Chapter 2. The Ramsey Number for Two Trees 17 and so, when m is odd, we have that R(K1, 2, K1, m) = m + 2. Case 2: m is even. If m is even, then m + 1 is odd. We begin by showing that R(K1, 2, K1, m) ≤ m + 1. Let G = Km + 1 be the complete graph of order m + 1. Let v be an arbitrary vertex of graph G and so deg v = m. Consequently, G is an m-regular graph. Assume, to the contrary, that in any red-blue coloring of the edges of G there is neither a red K1, 2 nor a blue K1, m. We consider the red subgraph GR of G. Let GR be a perfect matching graph with no two adjacent edges as in Figure 2.2.3. Otherwise, if GR has no perfect matching, then G contains a red K1, 2 which is a contradiction to our assumption. Figure 2.2.3: A red-blue coloring of edges of the complete graph Km + 1. 1 2 3 4 5 6 m− 1 m m + 1 Further we have the complement of GR as the blue subgraph GB of graph G. Then the vertices in the blue subgraph GB of G are either of degree m − 1 or m. If the vertex with degree m has all blue edges incident to it, then we have a blue K1, m, a contradiction to our assumption. If the vertex with degree m has one or more red edges incident to it, then we have a red K1, 2, again a contradiction to our assump- tion. Therefore, R(K1, 2, K1, m) ≤ m + 1. We now show that R(K1, 2, K1, m) > m. Let H be a complete graph of order m. We have that m is even. If v is an arbitrary vertex of H, then deg v = m− 1. Let C be the cycle that passes through every ver- tex of H exactly once. We use Theorem 1.2.1 to conclude that C is a Hamiltonian Chapter 2. The Ramsey Number for Two Trees 18 cycle in H, that is, C is a cycle that goes through each vertex of H exactly once. Let F = H − E(C). Then F is a regular graph of degree m− 2. Let there be a red-blue coloring of the edges of graph H. Color the edges of graph F blue and alternate the colors red and blue on the edges of C in the complete graph H. Then the red subgraph HR of H is 1-regular and the blue subgraph HB of H is m− 1 regular. As a result we have that there is a red-blue coloring of the edges of the complete graph H where there is neither a red K1, m nor a blue K1, 2. Therefore, we conclude that R(K1, 2, K1, m) > m. Consequently, we have that R(K1, 2, K1, m) = m + 1. 2.3 The Ramsey Number for Two Stars K1, n and K1, m In this section we prove the Ramsey number for two stars K1, n and K1, m of order n + 1 ≥ 3 and m + 1 ≥ 3 respectively. This results appeared in two articles: Recent results on generalized Ramsey Theory for graphs [16] and On Ramsey numbers for stars [8]. Harary in his article Recent results on generalized Ramsey Theory for graphs [16] only considered the Ramsey number for two stars of equal order, that is n = m. Burr and Roberts in their article On Ramsey numbers for stars [8] considered stars of all orders n + 1 ≥ 3 and m + 1 ≥ 3. We begin by proving the Ramsey number of two stars K1, n and K1, m where both n ≥ 2 and m ≥ 2 are even integers. Our proof is original. Chapter 2. The Ramsey Number for Two Trees 19 Proposition 2.3.1. Let n and m be even integers with n ≥ 2 and m ≥ 2. Then R(K1, n, K1, m) = n + m− 1. Proof Since n and m are even integers, let n = 2x and m = 2y for some positive integers x and y. We show that R(K1, n, K1, m) > n + m− 2. In this regard, let H be the complete graph of order n + m − 2. Since the order n + m− 2 of H is even, we have that H is 1-factorable by Theorem 1.2.3. If u is an arbitrary vertex in H, then deg u = (n + m− 2)− 1 = n + m− 3 = (n− 2) + (m− 1) = (n− 1) + (m− 2). That is, the graph H is 1-factorable into either (n− 2) + (m− 1) or (n− 1) + (m− 2) 1-factors. We now consider these two possibilities. Case 1: H is 1-factorable into (n− 2) + (m− 1) factors. Let there be a red-blue coloring of edges of the complete graph H. Color n− 2 edges of these 1-factors red and the remaining m− 1 edges of these 1-factors blue in H. The resulting red subgraph HR of H is a regular graph of degree n− 2 and the resulting blue subgraph is a regular graph of degree m− 1. Thus, there is a red-blue coloring of the edges of the complete graph H of order n + m− 2 where there is neither a red K1, n nor a blue K1, m. Chapter 2. The Ramsey Number for Two Trees 20 Case 2: H is 1 - factorable into (n− 1) + (m− 2) factors. We reflect consideration on the complete graph H with a red-blue coloring of edges. Color n− 1 edges of these 1-factors red and the remaining m− 2 edges of these 1- factors blue in H. The resulting red subgraph HR of H is a regular graph of degree n− 1 and the resulting blue subgraph HB of H is a regular graph of degree m− 2. Thus, there is a red-blue coloring of the edges of the complete graph H of order n + m− 2 where there is neither a red K1, n nor a blue K1, m. From the two cases above we may conclude that R(K1, n, K1, m) > n + m− 2. We now show that R(K1, n, K1, m) ≤ n + m− 1. In this regard, let G be the complete graph of order n + m− 1. If v is an arbitrary vertex of G, then deg v = (n + m− 1)− 1 = n + m− 2 = 2x + 2y− 2 = 2(x− 1) + 2y = 2x + 2(y− 1). Consequently, we see that the graph G is 2(x + y− 1)-regular, and so, by Theorem 1.2.4, we have that G is 2-factorable. The graph G is 2-factorable into (x − 1 + y) 2-factors. Assume to the contrary that in any red-blue coloring of the edges of the graph G there is neither a red K1, n nor a blue K1, m. We now consider two cases according to the grouping of the factors of G when we assign colors to the edges. Case 1: G is 2-factorable into (x− 1) + y factors. Consider a red-blue coloring of the edges of the graph G by coloring x− 1 edges of these 2-factors red and coloring the remaining y edges of these 2-factors blue. The Chapter 2. The Ramsey Number for Two Trees 21 resulting red subgraph GR of G is a regular graph of degree 2(x− 1) = 2x− 2 = n− 2 and the resulting blue subgraph GB of G is a regular graph of degree 2y = m. So we have that in any red-blue coloring of the edges of G there is always a blue K1, m since the blue subgraph GB of G is m-regular, a contradiction. Case 2: G is 2-factorable into [x + (y− 1)] 2-factors. Let there be a red-blue coloring of the edges of the graph G by coloring x of these 2-factors red and coloring the remaining y − 1 edges of these 2-factors blue. The resulting red subgraph GR of G is a regular graph of degree 2x = n and the resulting blue subgraph GB of G is a regular graph of degree 2(y− 1) = 2y− 2 = m− 2. So we have that in any red-blue coloring of the edges of G there is always a red K1, n since the red subgraph GR of G is n-regular, a contradiction. In both cases we get a contradiction, and so R(K1, n, K1, m) = n + m− 1. We now prove the Ramsey number for two stars K1, n and K1, m where both n ≥ 3 and m ≥ 3 are odd. When n = 1, then star K1, n is isomorphic to the path P2. From Chapter 2. The Ramsey Number for Two Trees 22 the article On Ramsey-type problems [15] authored by L. Gerencsér we have that R(P2, P2) = 2. Consequently, we have that R(K1, 1, K1, 1) = 2. Proposition 2.3.2. Let n and m be odd integers with n ≥ 3 and m ≥ 3. Then R(K1, n, K1, m) = n + m. Proof Since n and m are odd integers, let n = 2x + 1 and m = 2y + 1 for some positive integers x and y. We show that R(K1, n, K1, m) > n + m− 1. With that said, let H be the complete graph of order n + m− 1. If u is an arbitrary vertex of H, then deg u = (n + m− 1)− 1 = n + m− 2 = (2x + 1) + (2y + 1)− 2 = 2x + 2y. We see that the graph H is 2(x + y)-regular, and so by Theorem 1.2.4 we have that H is 2-factorable. The graph H is 2-factorable into (x + y) factors. Let there be a red- blue coloring of the edges of the complete graph H. Color x edges of these 2-factors red and the remaining y edges of these 2-factors blue in H. The red subgraph HR of H is a regular graph of degree 2x = n− 1 and the blue subgraph HR of H is regular graph of degree 2y = m− 1. Thus, we have that there is a red-blue coloring of the edges of H where there is a neither a red K1, n nor a blue K1, m, and so R(K1, n, K1, m) > n + m− 1. Chapter 2. The Ramsey Number for Two Trees 23 We now show that R(K1, n, K1, m) ≤ n + m. Let G be the complete graph of order n + m. If v is an arbitrary vertex in G, then deg v = (n + m)− 1. Hence G is a regular graph of degree n + m − 1. Consider a red-blue coloring of the edges of the complete graph G resulting in a red subgraph GR of G and a blue subgraph GB of G. Assume there is neither a red K1, n nor a blue K1, m in G. Table 2.3.1 gives all of the different ways to choose red and blue edges incident to vertex v. We conclude that if degGR v ≥ m, then G has a red K1, m, and if degGB v ≥ n, then G has a blue K1, n as indicated in the last column. Table 2.3.1: The number of red and blue edges incident to v in Kn + m. degGB v degGR v Contradiction 0 m + n− 1 red K1, m 1 m + n− 2 red K1, m 2 m + n− 3 red K1, m ... ... ... n− 1 m red K1, m n m− 1 blue K1, n n + 1 m− 2 blue K1, n ... ... ... m + n− 3 2 blue K1, n m + n− 2 1 blue K1, n m + n− 1 0 blue K1, n Consequently, in any red-blue coloring of edges of the complete graph G there is always either a red K1, m or a blue K1, n. Thus, R(K1, m, K1, n) ≤ n + m and so R(K1, m, K1, n) = n + m. Chapter 2. The Ramsey Number for Two Trees 24 We finally confirm the Ramsey number of two stars K1, n and K1, m where n ≥ 2 and m ≥ 2 are of opposite parity. Proposition 2.3.3. Let n and m be integers of opposite parity with n ≥ 2 and m ≥ 2. Then R(K1, n, K1, m) = n + m. Proof Since n and m are integers of opposite parity, let n = 2x and m = 2y + 1 for some positive integers x and y. We show that R(K1, n, K1, m) > n + m− 1. Let H be the complete graph of order n + m− 1. Since the order n + m− 1 of H is even, we have that H is 1-factorable by Theorem 1.2.3. If u is an arbitrary vertex in H, then deg u = (n + m− 1)− 1 = n + m− 2 = (n− 1) + (m− 1). The graph H is 1-factorable into (n− 1) + (m− 1) factors. Consider a red-blue col- oring of the edges of the complete graph H by coloring n− 1 edges of these 1-factors red and coloring the remaining m− 1 edges of these 1-factors blue. The resulting red subgraph HR of H is a regular graph of degree n− 1 and the resulting blue subgraph HB of H is a regular graph of degree m− 1. Consequently, there is a red-blue coloring of the edges of the complete graph H where there is neither a red K1, n nor a blue K1, m, and so R(K1, n, K1, m) > n + m− 1. We now show that R(K1, n, K1, m) ≤ n + m. Chapter 2. The Ramsey Number for Two Trees 25 Let G be the complete graph of order n + m. If v is an arbitrary vertex in G, then deg v = n + m− 1. We have that G is a regular graph of degree n + m− 1. Consider a red-blue coloring of the edges of the complete graph G resulting in a red subgraph GR of G and a blue subgraph GB of G. Assume there is neither a red K1, n nor a blue K1, m in G. In Table 2.3.2 we give all of the different ways to choose red and blue edges incident to vertex v. We see that if degGR v ≥ m, then G has a red K1, m, and if degGB v ≥ n, then G has a blue K1, n as indicated in the last column of Table 2.3.2. Table 2.3.2: The number of red and blue edges incident to v in Kn + m. degGB v degGR v Contradiction 0 m + n− 1 red K1, m 1 m + n− 2 red K1, m 2 m + n− 3 red K1, m ... ... ... n− 1 m red K1, m n m− 1 blue K1, n n + 1 m− 2 blue K1, n ... ... ... m + n− 3 2 blue K1, n m + n− 2 1 blue K1, n m + n− 1 0 blue K1, n Consequently, we have that in any red-blue coloring of the edges of the complete graph G there is always either a red K1, m or a blue K1, n. So we conclude that R(K1, m, K1, n) ≤ n + m and so R(K1, m, K1, n) = n + m. Chapter 2. The Ramsey Number for Two Trees 26 By combining Proposition 2.3.1, Proposition 2.3.2 and Proposition 2.3.3, we obtain Theorem 2.3.1. This result is used as the upper bound for the number of partite sets when we confirm the results in Chapter 3. Theorem 2.3.1. Let n and m be integers with n ≥ 2 and m ≥ 2. Then R(K1, n, K1, m) =  n + m− 1 if n and m are both even, n + m otherwise. 2.4 The Ramsey Number for a Star K1, m and a Tree T′n In this section we look at the Ramsey number of K1, m and T′n where T′n is a tree of order n ≥ 5 with a maximum degree of n− 2. The statement of Theorem 2.4.1 was given by Guo and Volkmann in their article Tree Ramsey numbers [9] in 1995, how- ever, for the sole purpose of maintaining similarity in the structure of the proof we use an original proof. We prove Theorem 2.4.1 in two propositions according to whether 2 | (m+ 1)(n− 1) or 2 - (m + 1)(n− 1). We begin by proving the Ramsey number for a star K1, m and a tree T′n when 2 | (m + 1)(n− 1). Proposition 2.4.1. If n > m + 1 ≥ 4 and 2 | (m + 1)(n− 1), then R(K1, m, T′n) = m + n− 2. Proof We show that R(K1, m, T′n) ≤ m + n− 2. In this regard, let G be the complete graph of order m + n − 2. If v is an arbitrary vertex of G, then deg v = (m + n− 2)− 1 = m + n− 3. Chapter 2. The Ramsey Number for Two Trees 27 Assume that in any red-blue coloring of the edges of the complete graph G there is neither a red K1, m nor a blue T′n. Consider a red-blue coloring of the edges of the complete graph G resulting in a red subgraph GR of G and a blue subgraph GB of G. Table 2.4.1 gives all of the different ways to choose red and blue edges incident to vertex v. We see that if degGR v ≥ m, then we have a red K1, m, and if degGB v ≥ n− 2, then we have a blue T′n as indicated in the last column of Table 2.4.1. Table 2.4.1: The number of red and blue edges incident to v in Kn + m− 2. degGR v degGB v Contradiction m + n− 3 0 red K1, m m + n− 4 1 red K1, m m + n− 5 2 red K1, m ... ... ... m n− 3 red K1, m m− 1 n− 2 blue T′n m− 2 n− 1 blue T′n ... ... ... 2 m + n− 5 blue T′n 1 m + n− 4 blue T′n 0 m + n− 3 blue T′n Consequently, every red-blue coloring of the edges of the complete graph G has a red K1, m or a blue T′n. We conclude that R(K1, m, T′n) ≤ m + n− 2. We now consider the lower bound, R(K1, m, T′n) > m + n− 3. Let H be the complete graph of order m + n− 3. If u is an arbitrary vertex in H, then deg u = (m + n− 3)− 1 = m + n− 4. Since 2 | (m + 1)(n− 1) we have that (m + 1)(n− 1) = 2q is even for some positive integer q. This implies that both m + 1 and n− 1 are even or one of m + 1 and n− 1 Chapter 2. The Ramsey Number for Two Trees 28 is even. We now consider these three cases. Case 1: Both m + 1 and n− 1 are even. Since both m + 1 and n − 1 are even, we have that both m and n are odd. That is m = 2x + 1 and n = 2y + 1 for some positive integers x and y. If u is an arbitrary vertex of H, then deg u = m + n− 4 = (2x + 1) + (2y + 1)− 4 = 2x + 2y− 2 = 2x + 2(y− 1) We find that the graph H is 2[x + (y − 1)]-regular and by Theorem 1.2.4, we have that H is 2-factorable into x + (y − 1) factors. Let there be a red-blue coloring of the edges of the complete graph H. Color x edges of these 2-factors red and the remaining y− 1 edges of these 2-factors blue. The resulting red subgraph HR of H is a regular graph of degree 2x = m− 1 and the resulting blue subgraph HB of H is a regular graph of degree 2(y− 1) = 2y− 2 = (n− 1)− 2 = n− 3. Thus, we have that there is a red-blue coloring of the edges of H where there is neither a red K1, m nor a blue T′n. For Case 1 we conclude that R(K1, m, T′n) > m + n− 3. Case 2: m + 1 is odd and n− 1 is even. Since m + 1 is odd, we have that m is even and since n− 1 is even, we have that n is odd. That is, m = 2x and n = 2y + 1 for some positive integers x and y. There- fore, the order m + n − 3 of H is even and, by Theorem 1.2.3, we have that H is Chapter 2. The Ramsey Number for Two Trees 29 1-factorable. Consequently, if u is an arbitrary vertex of H, then deg u = m + n− 4 = (m− 1) + (n− 3). The graph H is 1-factorable into (m− 1)+ (n− 3) factors. Let there be a red-blue col- oring of the edges of the complete graph H by coloring m− 1 edges of these 1-factors red and coloring the remaining n− 3 edges of these 1-factors blue. The resulting red subgraph of H is a regular graph of degree m− 1 and the resulting blue subgraph of H is a regular graph of degree n− 3. As a result we have that there is a red-blue coloring of edges of the complete graph H where there is neither a red K1, m nor a blue T′n. For Case 2, we conclude that R(K1, m, T′n) > m + n− 3. Case 3: m + 1 is even and n− 1 is odd. Since m+ 1 is even and n− 1 is odd, let that m = 2x+ 1 and n = 2y for some positive integers x and y. Consequently, we have m + n− 3 = (2x + 1) + (2y)− 3 = 2x + 2y− 2 = 2(x + y− 1) and so the order m + n − 3 of H is even. By Theorem 1.2.3 we have that H is 1- factorable. If u is an arbitrary vertex of H, then deg u = m + n− 4 = (m− 1) + (n− 3). Thus, the graph H is 1-factorable into (m− 1) + (n− 3) factors. Let there be a red- blue coloring of edges of the complete graph H. Color m− 1 edges of these 1-factors red and color remaining n− 3 edges of these 1-factors blue. The resulting red sub- graph of H is a regular graph of degree m− 1 and the resulting blue subgraph of H is a regular graph of degree n− 3. As a result we have that there is a red-blue coloring of the edges of the complete graph H where there is neither a red K1, m nor a blue T′n. For Case 3 we conclude that Chapter 2. The Ramsey Number for Two Trees 30 R(K1, m, T′n) > m + n− 3. Therefore, R(K1, m, T′n) = m + n− 2 in all three cases above. We now confirm the Ramsey number for a star K1, m and a tree T′n when 2 - (m + 1)(n− 1). Proposition 2.4.2. If n > m + 1 ≥ 4 and 2 - (m + 1)(n− 1), then R(K1, m, T′n) = m + n− 3. Proof Since 2 - (m + 1)(n − 1) we have that (m + 1)(n − 1) = 2a + 1 is odd for some positive integer a. For (m + 1)(n− 1) to be odd we have that both m + 1 and n− 1 are odd, implying that both m and n are even. Thus, m = 2x and n = 2y for some positive integers x and y. We begin by proving the upper bound R(K1, m, T′n) ≤ m + n− 3. Let G be the complete graph of order m + n− 3. If v is an arbitrary vertex of G, then deg v = (m + n− 3)− 1 = m + n− 4 = 2x + 2y− 4 = 2x + 2(y− 2) = 2(x− 1) + 2(y− 1). We find that the graph G is a 2(x + y− 2) regular graph which is 2-factorable into x + (y− 2) or (x − 1) + (y− 1) factors by Theorem 1.2.4. Assume that in any red- blue coloring of the edges of the complete graph G there is neither a red K1, m nor a blue T′n. We now consider these two cases. Chapter 2. The Ramsey Number for Two Trees 31 Case 1: G is 2-factorable into x + (y− 2) factors. Let there be a red-blue coloring of the edges of the complete graph G by assigning x edges of these 2-factors the color red and the remaining y− 2 edges of these 2-factors the color blue. The resulting red subgraph of G is a regular graph of degree 2x = m. Consequently, we have a red K1, m which is a contradiction to our assumption. For Case 1 we conclude that R(K1, m, T′n) ≤ m + n− 3. Case 2: G is 2-factorable into (x− 1) + (y− 1) factors. Let there be a red-blue coloring of edges of the complete graph G by assigning x− 1 edges of these 2-factors the color red and the remaining y− 1 edges of these 2-factors the color blue. The resulting blue subgraph of G is a regular graph of degree 2(y− 1) = 2y− 2 = n− 2. As a result, we have a blue T′n which is a contradiction to our assumption. For Case 2 we conclude that in any red-blue edge coloring of G there is always a blue T′n. Consequently, R(K1, m, T′n) ≤ m + n− 3. We now proof the lower bound R(K1, m, T′n) > m + n− 4. Let H be the complete graph of order m + n− 4. Since m and n are even, we have that the order of H is even and we have that H is 1-factorable by Theorem 1.2.3. Let u be an arbitrary vertex of H. Then deg u = (m + n− 4)− 1 = m + n− 5 = (m− 2) + (n− 3). The graph H is 1-factorable into (m− 2) + (n− 3) factors. Consider a red-blue color- ing of the edges of the complete graph H by assigning the color red to m− 2 edges of these 1-factors and the color blue to the remaining n− 3 edges of these 1-factors. The Chapter 2. The Ramsey Number for Two Trees 32 resulting red subgraph HR of H is a regular graph of degree m− 2 and the resulting blue subgraph HB of H is a regular graph of degree n− 3. Therefore, there exist a red-blue coloring of the edges of the complete graph H where there is neither a red K1, m nor a blue T′n. Consequently, R(K1, m, T′n) > m + n− 4, and so R(K1, m, T′n) = m + n− 3. By combining Proposition 2.4.1 and Proposition 2.4.2 we have Theorem 2.4.1. Theorem 2.4.1. For m ≥ 2 and n ≥ 5, R(K1, m, T′n) =  m + n− 2 if 2 | (m + 1)(n− 1), m + n− 3 if 2 - (m + 1)(n− 1). 2.5 The Ramsey Number for Two Trees In this section we prove the number R(T′m, T′n) of two trees of order m ≥ 5 and n ≥ 5 with maximum degree m − 2 and n − 2 respectively. In 1995 Guo and Volkmann did study the Ramsey number for two trees T′m and T′n in their article Tree-Ramsey numbers [9] and proved the result in Theorem 2.5.1 below. In the article Ramsey Number for Trees [17] Zhi-Hong Sun studied the Ramsey num- ber for a tree T′n and Gm where Gm is a connected graph of order m which need not be complete. Zhi-Hong Sun also considered the Ramsey number of two trees Tn” where Tn” is a tree on n vertices with V = {v0, v1, · · · , vn− 2, vn− 1} and E = {v0vi|1 ≤ i ≤ n− 3}⋃ {vn− 3vn− 2, vn− 2vn− 1}. Chapter 2. The Ramsey Number for Two Trees 33 Theorem 2.5.1. [17] If n and m are positive integers where n ≥ 5 and m ≥ 5, then R(T′m, T′n) =  m + n− 5 if m = n ≡ 0(mod 2), m + n− 3 if (m - 1) | (n− 3), m + n− 4 otherwise. We changed the statement in Theorem 2.5.1 to the statement in Theorem 2.5.2 below. In our analysis of the proof of Theorem 2.5.1 we observed that where we consider the complete graph on m + n − 3 vertices is covered by considering the complete graphs on m + n− 5 vertices and m− n− 4 vertices respectively. When considering the complete graph on m + n− 3 vertices Guo and Volkmann considered the condi- tion (m− 1) | (n− 3) implying that n− 3 = k(m− 1) for some positive integer k. This condition is covered in Theorem 2.5.2 with the following reasoning. Consider when m odd. Since m is odd, we have that m = 2a + 1 for some posi- tive integer a. Therefore n− 3 = k(m− 1) = k[(2a + 1)− 1] = k(2a) = 2ak. As a result, we have that n− 3 = 2ak which implies that n = 2ak + 3 = 2ak + (2 + 1) = 2(ak + 1) + 1 where ak + 1 is an integer. Therefore, we have that n is odd. The instance where both m and n are odd is covered when considering the complete graph on m + n− 4 vertices in Proposition 2.5.2. Chapter 2. The Ramsey Number for Two Trees 34 Consider m is even. Since m is even, we have that m = 2a for some positive in- teger a. Therefore, n− 3 = k(m− 1) = k(2a− 1). We now consider two instances according to the parity of k. If k is even, then we have that k = 2b for some positive integer b. Therefore, we have that n− 3 = k(2a− 1) = 2b(2a− 1) = 4ab− 2b and n = 4ab− 2b− 3 = 4ab− 2b− (2 + 1) = 4ab− 2b− 2− 1 = 2(2ab− b− 1)− 1 where 2(ab)− b− 1 is some positive integer. Thus, n is odd. The instance where m is even and n is odd is considered in Proposition 2.5.2. If k is odd, then we have that k = 2b + 1 for some positive integer b. Therefore, n− 3 = k(2a− 1) = (2b + 1)(2a− 1) = 4ab− 2b + 2a− 1 Chapter 2. The Ramsey Number for Two Trees 35 and n = 4ab− 2b + 2a− 1 + 3 = 4ab− 2b + 2a + 2 = 2(2ab− b + a + 1) where 2ab− b + a + 1 is a positive integer and so n is an even integer. The instance where both n and m are even is covered in Proposition 2.5.1. By the reasoning given above, we managed to simplify the statement of Theorem 2.5.1 to the statement given in Theorem 2.5.2. Theorem 2.5.2. If n and m are positive integers where n ≥ 5 and m ≥ 5, then R(T′m, T′n) =  m + n− 5 if m and n are both even, m + n− 4 otherwise. We prove Theorem 2.5.2 by considering the following two propositions according to the different parities of m and n. Proposition 2.5.1. Let m and n be positive integers where n ≥ 5 and m ≥ 5. If both m and n are even, then R(T′m, T′n) = m + n− 5. Proof We begin by proving the upper bound R(T′m, T′n) ≤ m + n− 5. Let G be the complete graph of order m + n− 5 and let v be an arbitrary vertex of G. Then deg v = (m + n− 5)− 1 = m + n− 6. Chapter 2. The Ramsey Number for Two Trees 36 Since we have that both m and n are even, let m = 2x and n = 2y for some positive integers x and y. Then, deg v = m + n− 6 = 2x + 2y− 6 = 2(x− 2) + 2(y− 1) = 2(x− 1) + 2(y− 2). We find that the graph G is a 2(x + y− 3)−regular graph and we have that G is 2- factorable into either (x− 2) + (y− 1) or (x− 1) + (y− 2) factors by Theorem 1.2.4. Assume that in any red-blue coloring of the edges of the complete graph G there is neither a red T′m nor a blue T′n. We consider two cases according to the factors of G. Case 1: G is 2-factorable into (x− 2) + (y− 1) factors. Let there be a red-blue coloring of the edges of the complete graph G. Color (x− 2) edges of these 2-factors red the remaining (y− 1) edges of these 2-factors blue in G. The resulting blue subgraph of G is a regular graph of degree 2(y− 1) = 2y− 2 = n− 2. Consequently, we have a blue T′n, which is a contradiction to our assumption. Thus, in any red-blue coloring of the edges of G there is always a blue T′n. Case 2: G is 2-factorable into (x− 1) + (y− 2) factors. Let there be a red-blue coloring of the edges of the complete graph G. Color (x− 1) edges in these 2-factors red and the remaining (y− 2) edges of these 2-factors blue. The resulting red subgraph of G is a regular graph of degree 2(x− 1) = 2x− 2 = m− 2. Consequently, we have a red T′m which is a contradiction. Thus, in any red-blue col- oring of the edges of G there is always a red T′m. Chapter 2. The Ramsey Number for Two Trees 37 From the two cases above we may conclude that R(T′m, T′n) ≤ m + n− 5. We now consider the lower bound, where we want to show that R(T′m, T′n) > m + n− 6. Let H be the complete graph of order m + n − 6. Since m and n are even we have that the order of H is even and by Theorem 1.2.3 we have that H is 1-factorable. If u is an arbitrary vertex of H, then deg u = (m + n− 6)− 1 = m + n− 7 = (m− 4) + (n− 3). The graph H is 1-factorable into (m − 4) + (n − 3) factors. Let there be a red-blue coloring of the edges of the complete graph H by coloring (m − 4) edges of these 1-factors red and remaining (n − 3) edges of the remaining 1-factors blue. The re- sulting red subgraph of H is a regular graph of degree m− 4 and the resulting blue subgraph of H is a regular graph of degree n− 3. Therefore, there is a red-blue coloring of edges of the complete graph H where there is neither a red Tm nor a blue T′n. As a result we get that R(T′m, T′n) > m + n− 6 and so R(T′m, T′n) = m + n− 5. Lastly, we need to consider when m and n are not both even. Chapter 2. The Ramsey Number for Two Trees 38 Proposition 2.5.2. Let m and n be positive integers where m ≥ 5 and n ≥ 5. If m and n are not both even, then R(T′m, T′n) = m + n− 4. Proof We begin by proving the upper bound R(T′m, T′n) ≤ m + n− 4. Let G be the complete graph of order m + n− 4. If v is an arbitrary vertex of G, then deg v = (m + n− 4)− 1 = m + n− 5. Assume to the contrary that in any red-blue coloring of the edges of the complete graph G there is neither a red T′m nor a blue T′n. Consider a red-blue coloring of the edges of G resulting in a red subgraph GR of G and a blue subgraph GB of G. In Table 2.5.1 we give all the possible colorings of the edges incident to vertex v. We see that if degGR v ≥ m− 2, then G has a red T′m, and if degGB v ≥ n− 2, then G has a blue T′n as indicated in the last column of Table 2.5.1. As a result in every red-blue coloring of the edges of the complete bipartite graph G there is always a blue T′n or a red T′m. As such we conclude that R(T′m, T′n) ≤ m + n− 4. We now consider the lower bound R(T′m, T′n) > m + n− 5. Let H be the complete graph of order m + n− 5. If u is an arbitrary vertex of H, then deg u = (m + n− 5)− 1 = m + n− 6. Since m and n are not both even, we have that either m and n are both odd or m and n are of opposite parity. We now consider these two cases. Chapter 2. The Ramsey Number for Two Trees 39 Table 2.5.1: The number of red and blue edges incident to v in Kn + m− 4. degGR v degGB v Contradiction m + n− 5 0 red T′m m + n− 6 1 red T′m m + n− 7 2 red T′m ... ... ... m− 1 n− 4 red T′m m− 2 n− 3 red T′m m− 3 n− 2 blue T′n m− 4 n− 1 blue T′n ... ... ... 2 m + n− 7 blue T′n 1 m + n− 6 blue T′n 0 m + n− 5 blue T′n Case 1: Both m and n are odd. If both m and n are odd, then we let m = 2x + 1 and n = 2y + 1 for some positive integers x and y. Therefore, deg u = m + n− 6 = (2x + 1) + (2y + 1)− 6 = 2x + 2y− 4 = 2(x− 1) + 2(y− 1). We have that H is a 2(x + y− 2)-regular graph. By theorem 1.2.4, we have that H is 2-factorable into (x− 1) + (y− 1) factors. Let there be a red-blue coloring of the edges of the complete graph H. Color (x− 1) of these 2-factors red and the remaining (y − 1) edges of these 2-factors blue. The Chapter 2. The Ramsey Number for Two Trees 40 resulting red subgraph of G is a regular graph of degree 2(x− 1) = 2x− 2 = (m− 1)− 2 = m− 3 and the resulting blue subgraph of G is a regular graph of degree 2(y− 1) = 2y− 2 = (n− 1)− 2 = n− 3. Consequently, we have that there is a red-blue coloring of the edges of the complete graph H where there is neither a red T′m nor a blue T′n. Case 2: m and n are of opposite parity. Without loss of generality, assume that m is even and n is odd. Thus, m = 2x and n = 2y + 1 for positive integers x and y. We have that the order of H is m + n− 5 = 2x + 2y + 1− 5 = 2x + 2y− 4 = 2(x + y− 2) which is even and, by Theorem 1.2.3, we have that H is 1-factorable. Thus, deg u = m + n− 6 = (m− 3) + (n− 3). and so H is 1-factorable into [(m− 3) + (n− 3)]. Assume, to the contrary, that in every red-blue coloring of the edges of the com- plete graph H there is always either a red T′m or a blue T′n. Reflect into consideration a red-blue coloring of the edges of the complete graph H by coloring (m− 3) edges of these 1-factors red and the remaining (n− 3) edges of these 1-factors blue. The Chapter 2. The Ramsey Number for Two Trees 41 resulting red subgraph of G is a regular graph of degree m− 3 and the resulting blue subgraph of G is a regular graph of degree n− 3. Consequently, we have that there is a red-blue coloring of the edges of the complete graph H where there is neither a red T′m nor a blue T′n. Consequently, R(T′m, T′n) > m + n− 5 and so R(T′m, T′n) = m + n− 4. 2.6 Conclusion This chapter mainly focuses on confirming the Ramsey number R(F, H) of two trees F and H. The result in Theorem 2.3.1 is used as an upper bound for the number of partite sets when dealing with k-Ramsey numbers in Chapter 3. Theorem 2.3.1 Let n and m be integers with n ≥ 2 and m ≥ 2. Then R(K1, n, K1, m) =  n + m− 1 if n and m are both even, n + m otherwise. We focus on confirming the Ramsey number R(K1, m, T′n) for a star of order m+ 1 ≥ 3 and a tree T′n of order n ≥ 5. Chapter 2. The Ramsey Number for Two Trees 42 Theorem 2.4.1 For m ≥ 2 and n ≥ 5, R(K1, m, T′n) =  m + n− 2 if 2 | (m + 1)(n− 1), m + n− 3 if 2 - (m + 1)(n− 1). We furthermore prove the Ramsey number R(T′m, T′n) for two trees of order m ≥ 5 and n ≥ 5, respectively. Theorem 2.5.2 If n and m are positive integers where n ≥ 5 and m ≥ 5, then R(T′m, T′n) =  m + n− 5 if m and n are both even, m + n− 4 otherwise. 43 Chapter 3 The k-Ramsey Number for Two Stars 3.1 Purpose The main aim of this chapter is to determine the k-Ramsey number Rk(K1, m, K1, n) for the pair of stars K1, m and K1, n of order m + 1 ≥ 3 and n + 1 ≥ 3 respectively. We are particularly interested in the case where k = 2 as this result is used to estimate the bipartite Ramsey number b(K1, m, K1, n) in Chapter 4. 3.2 The 2-Ramsey Number for Two Stars K1, 2 and K1, m The main objective of this section is to present a few background results. We notice that K1, 2 is isomorphic to P3 and so we have R2(K1, 2, K1, 2) = 2b(P3, P3)− 1.[18] The bipartite Ramsey number of two paths was studied by Faudree and Schelp in their article Path-path Ramsey-type Numbers for the Complete Bipartite graph [18]. From the article we have that R2(K1, 2, K1, 2) = 5. We now consider Rk(K1, n, K1, m) where variables k and n are fixed with k = 2 and n = 2. Theorem 3.2.1. [10] For each integer m ≥ 2, R2(K 2, K1, m) = 2m + 1. Chapter 3. The k-Ramsey Number for Two Stars 44 Proof We begin by proving the upper bound R2(K1, 2, K1, m) ≤ 2m + 1. Consider the balanced complete bipartite graph G of order 2m + 1. Let U be the partite set of G with m vertices and V be the partite set of G with m + 1 vertices. If u ∈ U, then deg u = m + 1. Consider a red-blue coloring of the edges of graph G resulting in a red subgraph GR of G and a blue subgraph GB of G. In Table 3.2.1 we give all of the different ways to choose red and blue of the edges incident to vertex u. We find that if degGR u ≥ m, then G has a red K1, m, and if degGB u ≥ 2, then G has a blue K1, 2 as indicated in the last column of Table 3.2.1. Therefore, we have a contradiction to our assumption and so R2(K1, 2, K1, m) ≤ 2m + 1. Table 3.2.1: The number of red and blue edges incident to u in K2m + 1. degGR u degGB u Contradiction m + 1 0 red K1, m m 1 red K1, m m− 1 2 blue K1, 2 m− 2 3 blue K1, 2 ... ... ... 2 m− 1 blue K1, 2 1 m blue K1, 2 0 m + 1 blue K1, 2 We now consider the lower bound b(K1, 2, K1, m) > m. In this regard, let H be the complete bipartite graph of order 2m where there is an equal number of vertices in the partite sets. If v is an arbitrary vertex in graph H, then deg v = m. By Theorem 1.2.5, we have that the graph H is 1-factorable. Thus, Chapter 3. The k-Ramsey Number for Two Stars 45 H is 1-factorable into m factors otherwise we have a red K1,2 or a blue K1, m in H. Consider a red-blue coloring of the edges of graph H by assigning the color red to one of these 1-factors and the color blue to the remaining m− 1 of these 1-factors as indicated in Figure 3.2.1. In Figure 3.2.1 we only colored the edges incident to one vertex in a partite set to avoid confusion. However, this coloring is repeated for all of the vertices in the partite set. Figure 3.2.1: A red-blue edge coloring of H. 1 2 3 4 m 1 2 3 4 m From the graph in Figure 3.2.1 we have that degHR v = 1 and degHB v = m− 1. We find that the resulting red subgraph of H is one regular and the resulting blue subgraph of H is m − 1 regular. Therefore, there exists a red-blue coloring of the edges of graph H where there is neither a red K1, 2 nor a blue K1, m. It follows that R2(K1, 2, K1, m) > 2m. and so, R2(K1, 2, K1, m) = 2m + 1. Chapter 3. The k-Ramsey Number for Two Stars 46 3.3 The k-Ramsey Number for Two Stars K1, n and K1, m This section focuses on the k-Ramsey number for two stars K1, n and K1, m where m, n ≥ 3. We are mainly interested with the instance where k = 2, however, we give the proof for the case where the number of vertices is divisible by the num- ber of partite sets, that is (m + n− 2) | (k − 1). This is because for the case where (m+ n− 2) - (k− 1) we have that k ≥ 3. For the other cases please refer to the article Stars and their k-Ramsey numbers [10]. We begin by confirming the upper bound for the k-Ramsey number of two stars K1, m and K1, n where m ≥ 2 and n ≥ 3. Proposition 3.3.1. Let k, n and m be positive integers with 2 ≤ k < R(K1, n, K1, m), m ≥ 3 and n ≥ 3. If m + n− 2 = (k− 1)q for some positive integer q, then Rk(K1, m, K1, n) ≤ kq + 1. Proof Consider the balanced complete k-partite graph G = K(k− 1)q, q + 1 of order kq + 1. Then G has k− 1 partite sets of order q and one partite set of order q + 1. If v is an arbitrary vertex from one of the partite sets of G with q vertices, then deg v = (k− 2)q + q + 1 = qk− 2q + q + 1 = qk− q + 1 = (k− 1)q + 1. This is the maximal degree of the balanced k-partite graph G and from the statement of the theorem we have that m + n− 2 = (k− 1)q. Chapter 3. The k-Ramsey Number for Two Stars 47 Consequently, we have deg v = (k− 1)q + 1 = (m + n− 2) + 1 = m + n− 1 = ∆G. Consider a red-blue coloring of the edges of graph G resulting in a red subgraph GR of G and a blue subgraph GB of G. In Table 3.3.1 we give all the different ways to choose red and blue edges incident to vertex v, the last column gives the graph we are trying to avoid. We find that if degGR v ≥ m, then G has a red K1, m, and if degGB v ≥ n, then G has a blue K1, n. Table 3.3.1: The number of red and blue edges incident to v in K(k− 1)q, q + 1. degGB v degGR v Contradiction 0 m + n− 1 red K1, m 1 m + n− 2 red K1, m 2 m + n− 3 red K1, m ... ... ... n− 1 m red K1, m n m− 1 blue K1, n n + 1 m− 2 blue K1, n ... ... ... m + n− 3 2 blue K1, n m + n− 2 1 blue K1, n m + n− 1 0 blue K1, n Thus, in every red-blue coloring of the edges of the balanced complete k-partite graph G there is always either a red K1, m or a blue K1, n which is a contradiction to our assumption. Hence, we conclude that Rk(K1, m, K1, n) ≤ kq + 1. Chapter 3. The k-Ramsey Number for Two Stars 48 We now confirm the k-Ramsey numbers of two stars K1, m and K1, n where m, n ≥ 3 and (k− 1)q is odd. Proposition 3.3.2. Let k, n and m be positive integers with 2 ≤ k < R(K1, n, K1, m), m ≥ 3 and n ≥ 3. If m + n− 2 = (k− 1)q for some positive integer q where (k− 1)q is odd, then Rk(K1, m, K1, n) = kq + 1. Proof Let (k − 1)q be odd. Due to the fact that the product of two integers is odd if and only if both integers are odd we have that k− 1 and q are both odd. Thus, k is even since k− 1 is odd. We show that Rk(K1, n, K1, m) = kq + 1. From Proposition 3.3.1 we only need to show that Rk(K1, n, K1, m) > kq. Consider the balanced complete k-partite graph H of order kq. Then H has k par- tite sets each of order q, that is H = Kkq. If v is an arbitrary vertex from one of the partite sets of H, then deg v = (k− 1)q. Hence graph H is a (k− 1)q-regular graph of degree n + m− 2. Since (k− 1)q = n + m− 2 is odd, it follows that n and m are of opposite parity. This is due to the fact that the sum of two integers is odd only if the integers are of opposite parity. Without loss of generality, let n be even and m be odd, that is n = 2x and m = 2y + 1 for some positive integers x and y. Let V1, V2, · · · , Vk denote the partite sets of V(H). Since k is even, we divide the partite sets Vi for 1 ≤ i ≤ k into k/2 pairs : {V1, V2}, {V3, V4}, · · · , {Vk− 1, Vk}. These k/2 pairs of partite sets bring about k/2 induced subgraphs H1, H2, · · · , Hk/2 isomor- phic to Kq, q. Let Mi be a perfect matching between V2i− 1 and V2i where 1 ≤ i ≤ k/2. Chapter 3. The k-Ramsey Number for Two Stars 49 Consider a subgraph F obtained by removing all of edges in the perfect matching Mi from H for 1 ≤ i ≤ k/2. Then F is a regular spanning subgraph of degree (k− 1)q− 1. If u is an arbitrary vertex of F, then deg u = (k− 1)q− 1 = (n + m− 2)− 1 = n + m− 3 = 2x + (2y + 1)− 3 = 2x + 2y− 2 = 2x− 2 + 2y = 2(x− 1) + 2y. Thus, the subgraph F is 2-factorbale into (x− 1) + y factors. Reflect into consideration a red-blue coloring of the edges of graph H by coloring (x − 1) edges in these 2-factors and each Mi red, where 1 ≤ i ≤ k/2, and the re- maining y edges in these 2-factors blue. The resulting red subgraph of H is a regular graph of degree 2(x− 1) + 1 = 2x− 2 + 1 = 2x− 1 = n− 1 and the resulting blue subgraph of H is a regular graph of degree 2y = m− 1. Thus, there is a red-blue coloring of the edges of graph H where there is neither a red K1, n nor a blue K1, m, and so Rk(K1, n, K1, m) > kq. Consequently, Rk(K1, n, K1, m) = kq + 1. The same result is attained if n is odd and m is even. Chapter 3. The k-Ramsey Number for Two Stars 50 We finally confirm the k-Ramsey number of two stars K1, m and K1, n where m ≥ 3, n ≥ 3 and (k− 1)q is even. Proposition 3.3.3. Let k, n and m be positive integers with 2 ≤ k < R(K1, n, K1, m), m ≥ 3 and n ≥ 3. If m + n− 2 = (k− 1)q for some positive integer q where (k− 1)q is even, then Rk(K1, m, K1, n) =  kq if k, q are both odd and n, m are both even, kq + 1 otherwise. Proof Let (k− 1)q be even. Then we have that either both k− 1 and q are even, or one of k − 1 and q is even. This is due to the fact that the product of any number by an even number is even. If (k− 1)q + 2 = n + m is even, then it follows that n and m are of the same parity. The sum of any two numbers of the same parity is even. We consider two cases; the first case we assume that both n and m are odd, and in the second case we assume that both are even. We show that Rk(K1, n, K1, m) = kq + 1, but from Proposition 3.3.1 we are only left with showing that Rk(K1, n, K1, m) > kq. Case 1: n and m are both odd. Let n = 2x + 1 and m = 2y + 1 for some positive integers n and m. Also let H be the balanced complete k-partite graph of order kq. Then H = Kkq has k partite sets each of order q. If v is an arbitrary vertex from one of the partite sets of H, then deg v = (k− 1)q = n + m− 2 = (2x + 1) + (2y + 1)− 2 = 2x + 2y + 2− 2 = 2x + 2y. Chapter 3. The k-Ramsey Number for Two Stars 51 This implies that H is a regular graph of degree (k− 1)q = 2x + 2y = 2(x + y). By Theorem 1.2.4 we have that H is 2-factorable into (x + y) factors. Reflect into consideration a red-blue coloring of the edges of the balanced complete k-partite graph H by coloring x edges of these 2-factors red and the remaining y edegs of these 2-factors blue. The resulting red subgraph of H is a regular graph of degree 2x = n− 1 and the resulting blue subgraph of H is a regular graph of degree 2y = m− 1. Therefor, there exists a red-blue coloring of the edges of graph H where there is neither a red K1, n nor a blue K1, m and so for Case 1 we have Rk(K1, n, K1, m) > kq. Case 2: n and m are both even. Let n = 2x and m = 2y for some positive integers x and y. Further, let (k− 1)q be even and so we have that either both k − 1 and q are even or one of k − 1 and q is even. We consider the three different subcases. Subcase 2.1: k− 1 is odd and q is even. Let H be the balanced complete k-partite graph of order kq. Then H has k-partite sets each of order q. If v is an arbitrary vertex from one of the partite sets of H, then deg v = (k− 1)q = n + m− 2 = 2x + 2y− 2 = 2(x− 1) + 2y. By Theorem 1.2.1, we have now that H is Hamiltonian. Let C be a Hamiltonian cycle that passes through all the vertices of H exactly once and let F be the spanning subgraph obtianed by removing the edges of C from H, that is, F = H − E(C). If u Chapter 3. The k-Ramsey Number for Two Stars 52 is an arbitrary vertex of F, then deg u = (k− 1)q− 2 = (n + m− 2)− 2 = 2x + 2y− 2− 2 = 2x− 2 + 2y− 2 = 2(x− 1) + 2(y− 1). Thus, F is a regular spanning subgraph of H of degree 2(x− 1) + 2(y− 1). Conse- quently, we see that the graph F is 2-factorable into (x− 1) + (y− 1) factors. Consider a red-blue coloring of the edges of graph H by coloring (x − 1) edges of these 2-factors red, coloring the remaining (y− 1) of these 2-factors blue, and alter- nating the colors red and blue to the edges of C. The resulting red subgraph of H is a regular graph of degree 2(x− 1) + 1 = 2x− 2 + 1 = 2x− 1 = n− 1 and the resulting blue subgraph of H is a regular graph of degree 2(y− 1) + 1 = 2y− 2 + 1 = 2y− 1 = m− 1. Therefor, there exists a red-blue coloring of the edges of graph H where there is neither a red K1, n nor a blue K1, m. So we have here Rk(K1, n, K1, m) > kq and so Rk(K1, n, K1, m) = kq + 1. Chapter 3. The k-Ramsey Number for Two Stars 53 Subcase 2.2: Both k− 1 and q are even. Let H = Kkq be the balanced complete k-partite graph of order kq. Then H has k partite sets each of order q. If v is an arbitrary vertex from one of the partite sets of H, then we find that deg v = (k− 1)q = n + m− 2 = 2x + 2y− 2 = 2x + 2y− 2 = 2(x− 1) + 2y. Thus, H is a regular graph of degree (k− 1)q = 2(x− 1) + 2y. Since k is odd, and q is even, let k = 2a + 1 and q = 2b for some positive integers a and b. Hence, n + m− 2 = (k− 1)q = (2a + 1− 1)(2b) = (2a)(2b) = 4ab. Since 4 | (n + m − 2), we write that n + m ≡ 2 (mod 4). Since both n and m are even, we have that one of n and m is congruent to 0 modulo 4 or 2 modulo 4, say n ≡ 0 (mod 4) and m ≡ 2 (mod 4). Then, since n ≡ 0 (mod 4), we have that 4 | n and so we have n = 4c for some positive integer c. Similarly, since m ≡ 2 (mod4) we have that 4 | (m− 2) and so we may write m− 2 = 4d for some positive integer d. By Theorem 1.2.1 we now have that H is Hamiltonian. Let C be a Hamiltonian cycle that goes through all the vertices of H once. Let F be the spanning subgraph ob- tained by removing the edges of C from H, that is F = H− E(C). If u is an arbitrary Chapter 3. The k-Ramsey Number for Two Stars 54 vertex of F, then we have that degF u = (k− 1)q− 2 = (n + m− 2)− 2 = 4c + (4d + 2)− 2− 2 = 4c + 4d− 2 = 2(2c− 1) + 4d. As a result, F is a regular spanning subgraph of H of degree 2(2c− 1) + 4d. Conse- quently, the graph F is 2-factorable into (2c− 1) + 2d factors. Consider a red-blue coloring of the edges of the balanced complete k-partite graph H by assigning the color red to the edges in (2c− 1) of these 2-factors, the color blue to the edges in the remaining 2d of these 2-factors, and alternate the colors red and blue to the edges of C. The resulting red subgraph of H is a regular graph of degree 2(2c− 1) + 1 = 4c− 2 + 1 = 4c− 1 = n− 1 and the resulting blue subgraph of H is a regular graph of degree 2(2d) + 1 = 4d + 1 = m− 1. That is, there is a red-blue coloring of the edges of graph H where there is neither a red K1, n nor a blue K1, m, and so Rk(K1, n, K1, m) > kq so in Subcase 2.2 we have Rk(K1, n, K1, m) = kq + 1. Subcase 2.3: k− 1 is even and q is odd. If k − 1 is even, then we have that (k − 1)q is even. This is due to the fact that the Chapter 3. The k-Ramsey Number for Two Stars 55 product of any number with an even number is even. So since (k− 1)q = n + m− 2 is even, it follows that both n and m is even. We want to show that Rk(K1, n, K1, m) > kq. Consider the balanced complete k-partite graph H of order kq. Then H has k partite sets each of order q, that is H = Kkq. If v is an arbitrary vertex of H, then deg v = (k− 1)q. Hence H is a regular graph of degree (k− 1)q. Consider a red-blue coloring of the edges of graph H resulting in a red subgraph of H and a blue subgraph of H. We claim that there is either a red K1, n or a blue K1, m in H. Note that H is a regular graph of degree (k− 1)q = n + m− 2 = (n− 1) + (m− 1). Thus, the graph H is 1-factorable into (n− 1) + (m− 1) factors. Assigning the color red to the edges in (n− 1) of these 1-factors results in a red subgraph of H of degree (n− 1) and assigning the color blue to the edges in (m− 1) of these 1-factors results in a blue subgraph of H of degree (m− 1). But (n − 1), (m − 1) and kq are odd. Thus our claim is true, and in any red-blue coloring of edges of the balanced complete k-partite graph H there is always either a red K1, n or a blue K1, m. Now we show that Rk(K1, n, K1, m) > kq− 1. Chapter 3. The k-Ramsey Number for Two Stars 56 Let F = Kq− 1, (k− 1)q be the balanced complete k-partite graph of order kq− 1. Then, F has one partite set of order q− 1 and k− 1 partite sets of order q. Let V1, V2, · · · , Vk− 1 be the partite sets of F having q vertices each. If u is an arbitrary vertex in Vi where 1 ≤ i ≤ k− 1, then we have deg u = (q− 1) + (k− 2)q = kq− 2q + q− 1 = kq− q− 1 = (k− 1)q− 1. Let Vk be the partite set of F having q− 1 vertices. If v is an arbitrary vertex in Vk, then we find that deg v = (k− 1)q = n + m− 2. Now, since both k and q are odd, let k = 2a + 1 and q = 2b + 1 for some positive integers a and b. We have that degv = n + m− 2 = (k− 1)q = (2a + 1− 1)(2b + 1) = 2a(2b + 1) = 4ab + 2a. We now reflect consideration on two subcases according to the parity of a. Chapter 3. The k-Ramsey Number for Two Stars 57 Subcase 2.3.1: a is even. Let a = 2x for some positive integer x. Then we have that (k− 1)q = n + m− 2 = 4ab + 2a = 4ab + 2(2x) = 4ab + 4x. We see that 4 | (n + m− 2) and so we have n + m ≡ 2 (mod 4). Since n and m are both even, we say without loss of generality, that one of n and m is congruent to 0 modulo 4 and the other is congruent to 2 modulo 4, that is, n ≡ 0 (mod 4) and m ≡ 2 (mod 4). Then, since n ≡ 0 (mod 4), we have that 4 | n and so we write that n = 4c for some positive integer c. Similarly, since m ≡ 2 (mod 4) we have that 4 | (m− 2) and so we write m− 2 = 4d for some positive integer d. Therefore, (k− 1)q− 2 = (n + m− 2)− 2 n + m− 4 = 4c + (4d + 2)− 4 = 4c + 4d− 2 = 4c− 2 + 4d = 2(2c− 1) + 4d. By Theorem 1.2.1 we have that F is a Hamiltonian graph. Let C be a Hamiltonian cycle in F that goes through all the vertices in F once. Note that the order of C is kq− 1. Let F′ be the spanning subgraph of F obtained by removing the edges of C from F, that is, F′ = F− E(C). If w is an arbitrary vertex of F′ from the partite set of F′ with q vertices, then deg w = (k− 2)q + q− 1− 2 = kq− 2q + q− 3 = kq− q− 3 = (k− 1)q− 3. Chapter 3. The k-Ramsey Number for Two Stars 58 If z is an arbitrary vertex of F′ from the partite set of F′ with q− 1 vertices, then deg z = (k− 1)q− 2. Thus, an arbitrary vertex in F′ is either of degree (k− 1)q− 2 or (k− 1)q− 3. Since k− 1 is even, we divide the partite sets V1, V2, · · · , Vk− 1 into (k− 1)/2 pairs, namely {V1, V2}, {V3, V4}, · · · , {Vk− 2, Vk− 1}. Let Mi be the perfect matching be- tween V2i− 1 and V2i where 1 ≤ i ≤ (k− 1)/2. Let F′′ be the regular multigraph produced from adding these ((k − 1)/2) perfect matchings to the graph F′. The multigraph F′′ is a regular graph of degree (k− 1)q− 3 + 1 = (k− 1)q− 2 = 2(2c− 1) + 4d. As a result the multigraph F′′ is 2-factorable into (2c− 1) + 2d factors. Consider a red-blue coloring of the edges of the multigraph F′′ by assigning the color red to the edges in (2c− 1) of these 2-factors, the color blue to the remaining edges in 2d of these 2-factors, and alternate the color red and blue to edges in C. The resulting red-subgraph F′′R of F is a regular graph of degree 2(2c− 1) + 1 = 4c− 2 + 1 = 4c− 1 = n− 1 and the resulting blue-subgraph F′′B of F is a regular graph of degree 2(2d) + 1 = 4d + 1 = m− 1. Since F is a subgraph of F′′ we have that the maximum degree of FR is less than or equal to n− 1, and the maximum degree of FB is less than or equal to m− 1, that is, Chapter 3. The k-Ramsey Number for Two Stars 59 ∆FR ≤ n− 1 and ∆FB ≤ m− 1. Thus there exists a red-blue coloring of the edges of graph F where there is neither a red K1, n nor a blue K1, m. Consequently, Rk(K1, n, K1, m) > kq− 1 and so Rk(K1, n, K)1, m = kq. Subcase 2.3.2: a is odd. Let a = 2x + 1 for some positive integer x. Then we have n + m− 2 = (k− 1)q = 4ab + 2a = 2a(2b + 1) = 2(2x + 1)(2b + 1) = (4x + 2)(2b + 1) = 4xb + 4x + 4b + 2 = 4(xb + x + b) + 2. Thus, n + m− 2 = 4(xb + x + b) + 2 and, therefore, n + m = 4(xb + x + b) + 4 = 4(xb + x + b + 1). We see that 4 | (n + m) and so n + m ≡ 0 (mod 4). Since n and m are both even, we have that either both n and m are congruent to 0 modulo 4 or both are congruent to 2 modulo 4. We first consider the case where both n and m are congruent to 0 modulo 4. Since n ≡ 0 (mod 4) and m ≡ 0 (mod 4), we have that 4 | n and 4 | m, and so we write Chapter 3. The k-Ramsey Number for Two Stars 60 n = 4c and m = 4d for some positive integers c and d. Thus, (k− 1)q− 2 = (n + m− 2)− 2 = n + m− 4 = 4c + 4d− 4 = 4c− 2 + 4d− 2 = 2(2c− 1) + 2(2d− 1). By Theorem 1.2.1 we have that F is a Hamiltonian graph. Let C be a Hamiltonian cycle in F that passes through all the vertices in F once. Note that the order of C is kq− 1. Let F′ be the spanning subgraph of F obtained by removing the edges of C from F, that is, F′ = F− E(C). If w is an arbitrary vertex of F′ from the partite set of F′ with q vertices, then, deg w = [(k− 2)q + q]− 1− 2 = kq− 2q + q− 3 = kq− q− 3 = (k− 1)q− 3. Further, let z be an arbitrary vertex of F′ from the partite set of F′ with q− 1 vertices. Then deg z = (k− 1)q− 2. As a result, we have that an arbitrary vertex in F′ is either of degree (k− 1)q− 2 or (k − 1)q − 3. From the condition of Subcase 2.3 we have that k − 1 is even and so we divide the partite sets V1, V2, · · · , Vk− 1 into (k − 1)/2 pairs, namely {V1, V2}, {V3, V4}, · · · , {Vk− 2, Vk− 1}. Let Mi be the perfect matching between V2i− 1 and V2i where 1 ≤ i ≤ (k− 1)/2. Let F′′ be the regular multigraph produced from adding these ((k − 1)/2) perfect Chapter 3. The k-Ramsey Number for Two Stars 61 matchings to the graph F′. The multigraph F′′ is a regular graph of degree (k− 1)q− 3 + 1 = (k− 1)q− 2 = n + m− 4 = 4c + 4d− 4 = 4c− 2 + 4d− 2 = 2(2c− 1) + 2(2d− 1). We have that the multigraph F′′ is 2-factorable into (2c− 1) + (2d− 1) factors. Then, consider a red-blue coloring of the edges of the multigraph F′′ by assigning the color red to edges in (2c− 1) of these 2-factors, the color blue to the remaining edges in (2d− 1) of these 2-factors, and alternate the color red and blue to edges in C. The resulting red subgraph F′′R of F is a regular graph of degree 2(2c− 1) + 1 = 4c− 2 + 1 = 4c− 1 = n− 1, and the resulting blue subgraph F′′B of F is a regular graph of degree 2(2d− 1) + 1 = 4d− 2 + 1 = 4d− 1 = m− 1. Since F is a subgraph of F′′, we have that the maximal degree of FR is less than or equal to (n− 1) and the maximal degree of FB is less than or equal to m− 1. That is ∆FR ≤ n− 1 and ∆FB ≤ m− 1. Therefor, Rk(K1, n, K1, m) > kq− 1. Therefor, Rk(K1, n, K)1, m = kq. Finally, consider the case where both n and m are congruent to 2 modulo 4. Since n ≡ 2 (mod 4) and m ≡ 2 (mod 4) we have that 4 | (n− 2) and 4 | (m− 2). So we Chapter 3. The k-Ramsey Number for Two Stars 62 write n− 2 = 4c and m− 2 = 4d for some positive integers c and d. Thus, (k− 1)q− 2 = (n + m− 2)− 2 = n + m− 4 = (4c + 2) + (4d + 2)− 4 = 4c + 4d = 2(2c) + 2(2d). Let C be a cycle in F that goes through all the vertices in F exactly once. The order of C is kq− 1. Then C is a Hamiltonian cycle and F is a Hamiltonian graph by Theorem 1.2.1. Let F′ be the spanning subgraph of F obtained by removing edges of C from F, that is, F′ = F− E(C). Let w be an arbitrary vertex of F′ from the partite set of F′ with q vertices. Then, deg w = [(k− 2)q + q]− 1− 2 = kq− 2q + q− 3 = kq− q− 3 = (k− 1)q− 3. Let z be an arbitrary vertex of F′ from the partite set of F′ with q− 1 vertices. Then, deg z = (k− 1)q− 2. Therefore, an arbitrary vertex in F′ is either of degree (k − 1)q − 2 or (k − 1)q − 3. Since k− 1 is even, we divide the partite sets V1, V2, · · · , Vk− 1 into (k− 1)/2 pairs, namely {V1, V2}, {V3, V4}, · · · , {Vk− 2, Vk− 1}. Let Mi be the perfect matching be- tween V2i− 1 and V2i where 1 ≤ i ≤ (k− 1)/2. Let F′′ be the regular multigraph produced from adding these ((k − 1)/2) perfect Chapter 3. The k-Ramsey Number for Two Stars 63 matchings to the graph F′. The multigraph F′′ is a regular graph of degree (k− 1)q− 3 + 1 = (k− 1)q− 2 = (n + m− 2)− 2 = n + m− 4 = (4c + 2) + (4d + 2)− 4 = 4c + 4d = 2(2c + 2d). As a result, the multigraph F′′ is 2-factorable into (2c + 2d) factors. Consider a red-blue coloring of the edges of the multigraph F′′ by assigning the color red to edges in 2c of these 2-factors, the color blue to the remaining edges in 2d of these 2-factors, and alternate the colors red and blue to edges in C. The resulting red subgraph F′′R of F is a regular graph of degree 2(2c) + 1 = 4c + 1 = (n− 2) + 1 = n− 1, and the resulting blue subgraph F′′B of F is a regular graph of degree 2(2d) + 1 = 4d + 1 = (m− 2) + 1 = m− 1. Since F is a subgraph of F′′, we have that the maximal degree of FR is less than or equal to n− 1 and the maximal degree of FB is less than or equal to m− 1, that is, ∆FR ≤ n− 1 and ∆FB ≤ m− 1. Thus, there exists a red-blue coloring of the edges of F where there is neither a red K1, n nor a blue K1, m, and so Rk(K1, n, K1, m)> kq− 1. Chapter 3. The k-Ramsey Number for Two Stars 64 Consequently, Rk(K1, n, K1, m) = kq. We combine the three propositions proved in Section 3.3 to give Theorem 3.3.1. The first proposition considered the upper bound and the last two propositions consid- ered the lower bound. The difference between Proposition 3.3.2 and Proposition 3.3.3 is about the parity of (k− 1)q. Diagram 3.3.1 Theorem 3.3.1 Proposition 3.3.1 Proposition 3.3.2 Proposition 3.3.3 Theorem 3.3.1. [10] Let k, n and m be positive integers with 2 ≤ k < R(K1, n, K1, m), m ≥ 3 and n ≥ 3. If m + n− 2 = (k− 1)q for some positive integer q, then Rk(K1, m, K1, n) =  kq if k and q are both odd and n and m are both even, kq + 1 otherwise. When k = 2, we have the following corollary. Corollary 3.3.1. Let k, n and m be positive integers with k = 2, m ≥ 3 and n ≥ 3. If m + n− 2 = q for some positive integer q, then R2(K1, n, K1, m) = 2q + 1. 3.4 Conclusion In this chapter we focused on confirming the k-Ramsey number, Rk(K1, m, K1, n) for two stars of order m, n ≥ 2. We began with a basic result where k = 2 and n = 2. That is we confirm the 2-Ramsey number Chapter 3. The k-Ramsey Number for Two Stars 65 R2(K1, 2, K1, m). We then considered the more general case where the number of vertices is divisible by the number of partite sets, that is (m + n− 2) | (k− 1). Theorem 3.3.1 Let k, n and m be positive integers with 2 ≤ k < R(K1, n, K1, m), m ≥ 3 and n ≥ 3. If m + n− 2 = (k− 1)q for some positive integer q, then Rk(K1, m, K1, n) =  kq if k and q are both odd and n and m are both even, kq + 1 otherwise. Consequently, if k = 2 then R2(K1, n, K1, m) = 2q + 1. 66 Chapter 4 The Bipartite Ramsey Number for Two Trees 4.1 Purpose The purpose of this chapter is to investigate the bipartite Ramsey number for a pair of bipartite graphs F and H, where F and H are different types of trees. We present a formula for the bipartite Ramsey number for a star and a tree T′n with n ≥ 5. 4.2 The Bipartite Ramsey Number for Two Stars K1, 2 and K1, m It is evident from Figure 4.2.1 that in every red-blue coloring of the edges of the complete bipartite graph of order two we always either have a red K1, 1 or a blue K1, 1. Trivially, we have that b(K1, 1, K1, 1) = 1. Figure 4.2.1: A red-blue coloring of edges of K1, 1 In 1998 Hattingh and Henning studied the bipartite Ramsey numbers for stars and paths in their article Star-path bipartite Ramsey numbers [13]. Note that the star K1, 1 is isomorphic to the path P2 and the star K1, 2 is isomorphic to the path P3. In this regard we have that b(K1, 1, K1, 2) = b(P2, K1, 2). From the article Star-path bipartite Ramsey numbers [13] we have that b(P2, K1, 2) = 2 and so b(K1, 1, K1, 2) = 2. Chapter 4. The Bipartite Ramsey Number for Two Trees 67 Since we already mentioned that K1, 2 and P3 are isomorphic graphs we have that b(P3, K1, m) = b(K1, 2, K1, m). We make use of the above result from Star-path bipartite Ramsey numbers [13] and Theorem 3.2.1, to determine b(K1, 2, K1, m), however, our proof is original. Theorem 4.2.1. For m ≥ 2, b(K1, 2, K1, m) = m + 1. Proof We show that b(K1, 2, K1, m)≤ m + 1. Consider the complete bipartite graph G of order 2m + 2, where each partite set is of order m + 1. If u is an arbitrary vertex of G, then deg u = m + 1. Think about a red-blue coloring of the edges of the complete bipartite graph G re- sulting in a red subgraph GR of G and a blue subgraph GB of G. In Table 4.2.1 below we give all the different ways to choose red and blue edges incident to vertex u in graph G and the last column represent the graph that appears because of the specific coloring. We see that if degGR u ≥ m, then G has a red K1, m, and if degGB u ≥ 2, then G has a blue K1, 2. As a result, in any red-blue coloring of the edges of the complete bipartite graph G there is always a blue K1, 2 or a red K1, m, and so b(K1, 2, K1, m) ≤ m + 1. We now want to show that b(K1, 2, K1, m) > m. Let H be the complete bipartite graph of order 2m where the order of each partite set is equal to m. If v is an arbitrary vertex of graph H, then deg v = m. Let M be a perfect matching between the two partite sets. Removing all the edges of M from H we have a spanning m− 1 regular subgraph F of H. Chapter 4. The Bipartite Ramsey Number for Two Trees 68 Table 4.2.1: The number of red and blue edges incident to u in Km + 1, m + 1. degGR u degGB u Contradiction m + 1 0 red K1, m m 1 red K1, m m− 1 2 blue K1, 2 m− 2 3 blue K1, 2 ... ... ... 2 m− 1 blue K1, 2 1 m blue K1, 2 0 m + 1 blue K1, 2 Consider a red-blue coloring of the edges of the complete bipartite graph H by as- signing the color blue to the edges of M and the color red to the edges of F. The resulting blue subgraph G is one regular and the resulting red subgraph of G is m− 1 regular. We have that there is a red-blue coloring of the edges of the complete bipartite graph H where there is neither a red K1, m nor a blue K1, 2. We conclude that b(K1, 2, K1, m) > m and consequently we have that b(K1, 2, K1, m) = m + 1. 4.3 The Bipartite Ramsey Number for Two Stars K1, n and K1, m This section focuses on finding the bipartite Ramsey number for two stars K1, n and K1, m of order n + 1 ≥ 3 and m + 1 ≥ 3 respectively. We consider n ≥ 2 and m ≥ 2 since, if n = m = 1, then both the stars K1, n and K1, m are isomorphic to the path P2 and Chapter 4. The Bipartite Ramsey Number for Two Trees 69 b(K1, 1, K1, 1) = b(P2, P2) = 1 from the article Path-path Ramsey-type numbers for complete bipartite graph [18] by Fau- dree and Schelp. Longani in 2003 considered the bipartite Ramsey number b(K1, n, K1, n) of stars where n ≥ 2 in the article Some Bipartite Ramsey numbers [19]. In our dissertation we extend the study of Longani to the bipartite Ramsey number b(K1, n, K1, m) of stars where n, m ≥ 2 and n and m are not necessarily equal to each other. The following is our own original work. Theorem 4.3.1. Let m, n be positive integers with m ≥ 2 and n ≥ 2. If m+ n− 2 = q for some positive integer q, then b(K1, n, K1, m) = q + 1. Proof We begin by proving that b(K1, n, K1, m) ≤ q + 1. Let G be the complete bipartite graph of order 2q + 2 = 2(m + n − 1). If u is an arbitrary vertex of G, then deg u = q + 1 = (m + n− 2) + 1 = m + n− 1. Consider a red-blue coloring of the edges of G that results in a red subgraph GR of G and a blue subgraph GB of G. In Table 4.3.1 below we give all the different ways to choose red and blue edges incident to vertex u in G and in the last column we give the graph we are trying to avoid but exists due to a specific coloring. We see that if degGR u ≥ m, then G has a red K1, m, and if degGB u ≥ n, then G has a blue K1, n. As a result in every red-blue coloring of the edges of the complete bipartite graph G there is always a blue K1, n or a red K1, m. As such, we proved that Chapter 4. The Bipartite Ramsey Number for Two Trees 70 b(K1, n, K1, m) ≤ q + 1. Table 4.3.1: The number of red and blue edges incident to u in Km + n− 1, m + n− 1. degGR u degGB u Contradiction m + n− 1 0 red K1, m m + n− 2 1 red K1, m m + n− 3 2 red K1, m ... ... ... m n− 1 red K1, m m− 1 n blue K1, n m− 2 n + 1 blue K1, n ... ... ... 2 m + n− 3 blue K1, n 1 m + n− 2 blue K1, n 0 m + n− 1 blue K1, n We now consider the lower bound b(K1, n, K1, m) > q. Let H be the complete bipartite graph of order 2q where each partite set has q ver- tices. By Theorem 1.2.5 we have that for every positive integer q the graph H is 1-factorable. Thus, H is a q-regular bipartite graph and for any arbitrary vertex u of H we have that deg u = q = m + n− 2 = (m− 1) + (n− 1). The graph H is 1-factorable into (m− 1) + (n− 1) factors. Reflect into considera- tion a red-blue coloring of the edges of the complete bipartite graph H by coloring (m− 1) edges of the 1-factors red the remaining (n− 1) edges of these 1-factors blue. The resulting red subgraph of H is an (m− 1)-regular graph and the resulting blue subgraph of H is an (n− 1)-regular graph. Chapter 4. The Bipartite Ramsey Number for Two Trees 71 Thus, there is a red-blue coloring of the edges of the complete bipartite graph H where there is neither a red K1, m nor a blue K1, n. We conclude that b(K1, n, K1, m) > q and so b(K1, n, K1, m) = q + 1 = (m + n− 2) + 1 = m + n− 1. From our study on bipartite Ramsey numbers for two stars we discovered the fol- lowing result. We give a proof for this discovery below. Proposition 4.3.1. For n ≥ 2 and m ≥ 2, R2(K1, n, K1, m) = 2b(K1, n, K1, m)− 1. Proof From Theorem 4.3.1 we have that b(K1, n, K1, m) = q + 1 = m + n− 1 where q = m + n − 2. In the proof of Theorem 4.3.1 we show that in a complete bipartite graph Kq, q there is neither a red K1, n nor a blue K1, m. We further show in the proof of Theorem 4.3.1 that in any red-blue coloring of the edges of the complete bipartite graph Kq + 1, q + 1 there is always either a red K1, n or a blue K1, m. We now investigate the intermediate complete bipartite graph Kq, q + 1. Let G be the complete bipartite graph of order 2q + 1 where V is the partite set of G Chapter 4. The Bipartite Ramsey Number for Two Trees 72 with q vertices and U is the partite set of G with q + 1 vertices. If v ∈ V, then deg v = q + 1 = (m + n− 2) + 1 = m + n− 1. Consider a red-blue coloring of the edges of the complete bipartite graph G resulting in a red subgraph GR of G and a blue subgraph GB of G. In Table 4.3.2 we give all the different ways to choose red and blue edges incident to vertex v in G and the last column of the table gives us the graph we are trying to avoid, but which occurs according to how the colors are assigned. We have that if degGR v ≥ n, then G has a red K1, n, and if degGB v ≥ m, then G has a blue K1, m. Table 4.3.2: The number of red and blue edges incident to v in Kq, q + 1. degGB v degGR v Contradiction m + n− 1 0 blue K1, m m + n− 2 1 blue K1, m m + n− 3 2 blue K1, m ... ... ... m + 1 n− 2 blue K1, m m n− 1 blue K1, m m− 1 n red K1, n m− 2 n + 1 red K1, n ... ... ... 2 m + n− 3 red K1, n 1 m + n− 2 red K1, n 0 m + n− 1 red K1, n As a result we have that in any red-blue coloring of edges of the complete bipartite graph G there is always either a blue K1, m or a red K1, n which is a contradiction to Chapter 4. The Bipartite Ramsey Number for Two Trees 73 our assumption. Therefore, R2(K1, n, K1, m) = 2q + 1 = 2(m + n− 2) + 1 = 2m + 2n− 4 + 1 = 2m + 2n− 2− 2 + 1 = 2m + 2n− 2− 1 = 2(m + n− 1)− 1 = 2b(K1, n, K1, m)− 1. 4.4 The Bipartite Ramsey Number for a Star K1, m and a Tree T′n In 2013 Christou, Iliopoulos and Miller studied the bipartite Ramsey number of sim- pler monochromatic graphs such as