Bipartite Ramsey numbers involving stars, stripes and trees

Michalis Christou^a , Costas S. Iliopoulosa,b, Mirka Millerc,d,^∗

michalis.christou@kcl.ac.uk, csi@dcs.kcl.ac.uk, mirka.miller@newcastle.edu.au

The Ramsey number R(m, n) is the smallest integer p such that any blue-red colouring of the edges of the complete graph K^p forces the appearance of a blue K^m or a red Kn. Bipartite Ramsey problems deal with the same questions but the graph explored is the complete bipartite graph instead of the complete graph. We investigate the appearance of simpler monochromatic graphs such as stripes, stars and trees under a 2-colouring of the edges of a bipartite graph. We give the Ramsey numbers Rb(mP2, nP2), Rb(Tm, Tn), Rb(Sm, nP2), Rb(Tm, nP2) and Rb(Sm, Tn).

Keywords: bipartite Ramsey theory, stars, stripes, trees

Mathematics Subject Classification : 05C55

Introduction

Extremal graph theory problems usually ask for the max/ min order or size of a graph having certain characteristics. Such questions are often quite natural in the construction of networks or circuits. Ramsey theory explores the question of how big a structure must be to contain a certain substructure or substructures (for a list of applications see [20]).

Ramsey [19] showed that in a blue-red colouring of the edges of a sufficiently large complete graph there must exist either a blue or a red complete subgraph of a given order. The minimum order of a complete graph that must achieve that is known as a Ramsey number. Since then large

^aDepartment of Informatics, King's College London, UK

^bDigital Ecosystems & Business Intelligence Institute, Curtin University, Australia

^cSchool of Mathematical and Physical Sciences, The University of Newcastle, Australia

^dDepartment of Mathematics, University of West Bohemia,Czech Republic

^∗This research was supported by a Marie Curie International Incoming Fellowship within the 7th European Community Framework Programme.

Received: 24 May 2013, Revised: 4 September 2013, Accepted: 14 September 2013.

amount of research has been done trying to obtain exact values for Ramsey numbers, or to obtain good lower and upper bounds[18].

There are many generalizations of Ramsey theory. Multicolour Ramsey theory deals with the same problem involving more than two colours. Infinite Ramsey theory investigates similar problems on infinite graphs. Ramsey numbers also exist for monochromatic graphs other than complete subgraphs, e.g. trees, stars, bipartite graphs, cycles, paths, etc. Bipartite Ramsey problems deal with the same questions but the graph explored is the complete bipartite graph instead of the complete graph. Additionally, there are many similar questions for directed graphs.

The bipartite case has been studied extensively. In particular, research has been done to obtain exact values for small Ramsey numbers ([1, 8, 12, 17]). A first general upper bound was given by Irving [15] by exploring the similarity of the problem with Zarankiewicz's problem. Subsequent work on general bounds for the problem was given by Thomason et al[22], by Hattingh et al. [12], by Goddard et al. [10], by Caro et al. [4], by Conlon [6] and Lin et al. [16]. Exact solutions were given for simpler cases of the problem such as path-path bipartite Ramsey numbers [9, 11], star-star bipartite Ramsey numbers [17], star-path bipartite Ramsey numbers [13], K2,2-K1,n and K2,2-K2,n bipartite Ramsey numbers [2], C2m-K2,² bipartite Ramsey numbers [21] and bipartite Ramsey numbers for multiple copies of K2,² [14]. Some variations of the bipartite case such as multicolour problems [3, 5] and rainbow colouring problems [7] have been also studied.

In this paper we consider special cases of the bipartite Ramsey problem. More specifically we investigate the appearance of simpler monochromatic graphs such as stripes, stars and trees under a 2-colouring of the edges of a bipartite graph. We give the Ramsey numbers Rb(mP2, nP2), Rb(Tm, Tn), Rb(Sm, nP2), Rb(Tm, nP2) and Rb(Sm, Tn).

1. Definitions and Problems

Throughout this paper we consider an undirected graph G(V, E), where V is the set of vertices, also called nodes, and E is the set of edges. The complement graph G(V, E) of G has the same vertices as G but edges that appear in G do not appear in G and edges that do not appear in G appear in G. The order of a graph is the number of its vertices. The size of a graph is the number of its edges. A path Pn(V, E) is a graph with V = {x1, x2, . . . , xn} and E = {x1x2, x2x3, . . . , xn−1xn}. Its end vertices are x1, xⁿ and its length ` is equal to n − 1. A cycle Cn(V, E), where n ≥ 3, is a graph with V = {x1, x2, . . . , xn} and E = {x1x2, x2x3, . . . , xn−1xn, xnx1}. Its length ` is equal to n. A cycle is called odd/even if its length is odd/even. The girth g of a graph G is the length of its shortest cycle. A graph containing no cycles is called an acyclic graph. The degree of a vertex v ∈ G is denoted by d(v) and is equal to the number of vertices to which v is connected. A regular graph is a graph in which all its vertices have the same degree. A graph is planar if it can be drawn in a plane without its edges crossing. A face is a region surrounded by a cycle in a planar embedding of a graph without any path crossing the cycle. A tree Tⁿ is a maximal acyclic graph on n vertices. A forest is a disconnected acyclic graph. A rooted tree has a node which is called the root. In such a tree, each of the nodes that is one graph edge further away from a given node (parent) and its distance to the root is one more than its parent is called a child. Nodes having the same parent node are called siblings. The height of a tree Tn, denoted by Height(Tn), is defined as the maximum length of a path from the root of Tⁿ to a leaf of Tn. A star Sⁿ of order n, is a

tree on n nodes with one node having degree n − 1 and the other n − 1 nodes having degree 1. A complete graph on n vertices, denoted by Kn, is a graph in which all n vertices are connected to each other. A bipartite graph is a graph in which all its vertices are decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A complete bipartite graph on 2n vertices, denoted by Kn,n, is a bipartite graph in which every pair of vertices belonging in a different partition are adjacent. A nP² stripe graph is the graph consisting of 2n vertices and n independent edges.

The Ramsey number R(m, n) is the smallest integer p such that any blue-red colouring of the edges of the complete graph K^p forces the appearance of a blue K^m or a red Kn.

The bipartite Ramsey number Rb(m, n) is the smallest integer p such that any blue-red colouring of the edges of the complete bipartite graph Kp,p forces the appearance of a blue Km,m or a red Kn,n.

More generally the bipartite Ramsey number Rb(H, G), where H and G are bipartite graphs, is the smallest integer p such that any blue-red colouring of the edges of the complete bipartite graph Kp,p forces the appearance of a blue H or a red G.

2. Bipartite Ramsey numbers involving stars, stripes and trees

In this section we will give solutions to the problems that we are considering. For the first four problems we first give an upper bound and then we prove that it is tight. However the bipartite Ramsey numbers for trees appear to be smaller in the case that both of the considered trees are of even order. In the last case we first give an upper bound, then we show when it can be achieved and we give the exact solutions for the rest of its cases.

The solution to the bipartite Ramsey stripe problem is an immediate consequence of the following theorem.

Theorem 2.1. \[R_b(mP_2, nP_2) = m + n - 1.\]

Proof. We will first prove that Rb(mP2, nP2) ≤ m + n − 1 by considering a 2-colouring of Kb,b, where b = m + n − 1. We pick a maximal Kk,k containing a blue kP2. If k ≥ m we have a blue mP² otherwise maximality forces a red Kb−k,b−^k made from the remaining vertices. That means a red (b − k)P2. But k < m and so b − k > (n + m − 1) − m. Hence b − k ≥ n.

The following lower bound shows that Rb(mP2, nP2) > m +n−2. We consider the following 2-colouring of Km+n−2,m+n−² (see also Figure 1):

• Let the independent sets of Km+n−2,m+n−² be A and B.
• We colour the edges joining the first m − 1 vertices of A to the vertices of B.
• We colour the rest of the edges red.

Figure 1: A 2 colouring of \(K_{6.6}\) without a blue (continuous line) \(5P_2\) or a red (dashed line) \(3P_2\)

The solution for the bipartite Ramsey tree problem is broken into five lemmas as shown below, depending on whether the considered trees are both of even order and whether the orders of the considered trees are close enough.

Theorem 2.2.

\[R_b(T_m, T_n) = \begin{cases} m - 1, & m = n = 2k, \\ k \in \mathbb{Z}^+ \\ max(min(m, n), max(\lceil \frac{m}{2} \rceil, \lceil \frac{n}{2} \rceil)), & \textit{otherwise}. \end{cases}\]

Proof. W.l.o.g. we consider \(2 \le m \le n\). The general upper bound is given by Lemma 2.1. The construction of Lemma 2.2 gives the lower bound for the case \(m < \lceil \frac{n}{2} \rceil\). The construction of Lemma 2.3 gives the lower bound for the case \(m \ge \lceil \frac{n}{2} \rceil\), with the restriction that m and n cannot be equal if they are both even. A stricter upper bound in the case that m is even and m = n is given by Lemma 2.4 and finally the construction of Lemma 2.5 gives the lower bound for this case. \(\square\)

The following lemma gives us the general upper bound for this problem.

Lemma 2.1. \[R_b(T_m, T_n) \leq max(m, \lceil \frac{n}{2} \rceil)\], where \(2 \leq m \leq n\).

Proof. Consider a 2-colouring of \(K_{b,b}\), where \(b = max(m, \lceil \frac{n}{2} \rceil)\). Let the independent sets of \(K_{b,b}\) be A and B. Consider a maximal red \(T_k\). W.l.o.g. say it is made by the first x vertices in A and the first k-x vertices of B. If k=b we get a red \(T_{2b}\) (i.e. at least a \(T_n\)), otherwise maximality forces a blue \(K_{b-x,k-x}\) (composed by the last b-x vertices of A and the first k-x vertices of A and so a blue \(K_{x,b+x-k}\) (composed by the first A vertices of A and the last A vertices of A and so a blue A vertices of A and a blue A vertices of A and the last A vertices of A and so a

Therefore, there is at least one blue \(T_b\) (even k) or at least one blue \(T_{b+1}\) (odd k) and hence in either case there exists at least a blue \(T_m\).

The following lemma gives us a lower bound for this problem for the case where \(2 \le m < \lceil \frac{n}{2} \rceil\).

Lemma 2.2. \[R_b(T_m, T_n) > \lceil \frac{n}{2} \rceil - 1\], where \(2 \le m < \lceil \frac{n}{2} \rceil\).

Proof. A red \(K_{\lceil \frac{n}{2} \rceil - 1, \lceil \frac{n}{2} \rceil - 1}\) contains at most a red \(T_{n-2}\) (even n) or at most a red \(T_{n-1}\) (odd n). \(\square\)

The following lemma gives us a lower bound for this problem for the case where \(2 \le \lceil \frac{n}{2} \rceil \le m < n\) or 2 < n = m = 2k + 1 with \(k \in \mathbb{Z}^+\).

Lemma 2.3. \(R_b(T_m, T_n) > m-1\), where \(2 \leq \lceil \frac{n}{2} \rceil \leq m < n \text{ or } 2 < n = m = 2k+1\) with \(k \in \mathbb{Z}^+\).

Proof. Consider the following 2-colouring of \(K_{m-1,m-1}\) (see also Figure 2a):

• Let the independent sets of \(K_{m-1,m-1}\) be A and B.
• Colour the edges joining the first \(\lfloor \frac{m-1}{2} \rfloor\) vertices of A with the first \(\lceil \frac{m-1}{2} \rceil\) vertices of B blue.
• Colour the edges joining the last \(\lceil \frac{m-1}{2} \rceil\) vertices of A with the last \(\lfloor \frac{m-1}{2} \rfloor\) vertices of B blue.
• Colour the rest of the edges red.

The following lemma gives us a lower upper bound for this problem for the case where m=n=2k with \(k \in \mathbb{Z}^+\).

Lemma 2.4. \(R_b(T_m, T_m) \leq m - 1\) if m is even.

Proof. Consider a 2-colouring of \(K_{m-1,m-1}\). Let the independent sets of \(K_{m-1,m-1}\) be A and B. By previous lemma it contains either a blue \(T_{m-1}\) or a red \(T_{m-1}\). W.l.o.g. say a blue \(T_{m-1}\) made by the first x vertices in A and the first m-1-x vertices of B. Maximality forces a red \(K_{m-1-x,m-1-x}\) (composed by the last m-1-x vertices of A and the first m-1-x vertices of A and the last A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and the last A vertices of A and so a red A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last A vertices of A and the last

The following lemma shows that the upper bound established in the previous lemma can be achieved.

Lemma 2.5. \(R_b(T_m, T_m) > m - 2\) if n = m = 2k.

Proof. Let b = min(m, n). Consider the following 2-colouring of \(K_{m-2,m-2}\) (see also Figure 2b):

• Let the independent sets of \(K_{m-2,m-2}\) be A and B.
• Colour the edges joining the first \(\lfloor \frac{m-1}{2} \rfloor\) vertices of A with the first \(\lfloor \frac{m-1}{2} \rfloor\) vertices of B blue.
• Colour the edges joining the last \(\lfloor \frac{m-1}{2} \rfloor\) vertices of A with the last \(\lfloor \frac{m-1}{2} \rfloor\) vertices of B blue.
• Colour the rest of the edges red.

The solution to the bipartite star vs stripes problem is an immediate consequence of the following theorem.

Theorem 2.3. \(R_b(S_m, nP_2) = m + \lfloor \frac{n-1}{2} \rfloor - 1.\)

(a) A 2 colouring of \(K_{5,5}\) without a blue (continuous line) \(T_6\) or a red (dashed line) \(T_8\)

(b) A 2 colouring of \(K_{6,6}\) without a blue (continuous line) \(T_8\) or a red (dashed line) \(T_8\)

Figure 2: Lower bound constructions considered in Theorem 2.2

Proof. We will first prove that \(R_b(S_m, nP_2) \leq m + \lfloor \frac{n-1}{2} \rfloor - 1\). Let's consider a 2-colouring of \(K_{b,b}\), where \(b = m + \lfloor \frac{n-1}{2} \rfloor - 1\). Let the independent sets of \(K_{b,b}\) be A and B. Consider a maximal red \(kP_2\), \(k \leq n-1\). W.l.o.g. say it is made by the first k vertices in A and the first k vertices of B. Maximality forces a blue \(K_{b-k,b-k}\) (composed by the last b-k vertices of A and the last b-k vertices of A and the last A0 vertices of A1 and so a blue A1. Maximality of the red A2 also forces at least one of the two vertices of A2 in the upper sets to be joined with only blue edges to the lower sets. Therefore there exist a vertex in the lower sets with A1 we get at least a blue A2 blue edges attached on it, i.e. at least a blue A3 blue A4 blue A5 blue edges attached on it, i.e. at least a blue A6 blue A6 blue edges attached on it, i.e. at least a blue A6 blue edges edges edges attached on it, i.e. at least a blue A6 blue edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges edges e

\[R_b(S_m, nP_2) > m + \lfloor \frac{n-1}{2} \rfloor - 2.\]

Let \(c = m + \lfloor \frac{n-1}{2} \rfloor - 2\). We consider the following 2-colouring of \(K_{c,c}\) (see also Figure 3):

• Let the independent sets of \(K_{c,c}\) be A and B.
• \(\bullet\) Colour the edges joining the first m-2 vertices of A with the first m-2 vertices of B blue.
• Colour the rest of the edges red.

Figure 3: A 2 colouring of \(K_{6.6}\) without a blue (continuous line) \(S_6\) or a red (dashed line) \(5P_2\)

The soution to the bipartite tree vs stripes problem is an immediate consequence of the following theorem.

Theorem 2.4. \[R_b(T_m, nP_2) = max(n, \lceil \frac{m+n-1}{2} \rceil).\]

Proof. We will first show that Rb(Tm, nP2) ≤ max(n, d m+n−1 2 e). We consider a 2-colouring of Kb,b, where b = d m 2 e + n − 1. Let the independent sets of Kb,b be A and B. Consider a maximal red kP2. W.l.o.g. say it is made by the first k vertices in A and the first k vertices of B. If k = b then we get a red nP² otherwise 0 < k < b and maximality forces a blue Kb−k,b−^k (composed by the last b − k vertices of A and the last b − k vertices of B) and so a blue T2b−2k. Therefore there exists at least one blue T2b−2n+2 in our graph, i.e. at least one blue Tm. Maximality of the red kP² also forces at least one of the two vertices of a P² in the first sets of A and B to be joined with only blue edges to the lower sets. This forces the appearance of at least a blue T2(b−k)+^k = T2b−^k composed by the vertices of the last sets of A and B and at least k vertices from the upper sets of A and B, i.e at least a blue T2^d m+n−1 2 e−n+1 (which means a blue T^m if m + n − 1 is even or a blue Tm+1 if m + n − 1 is odd).

We will now show that Rb(Tm, nP2) > d m+n−1 2 e − 1. Let c = d m+n−1 2 e − 1. Consider the following 2-colouring of Kc,c (similar to the colouring given in Figure 3):

• Let the independent sets of Kc,c be A and B.
• Colour the edges joining the first b m−1 2 c vertices of A with the first d m−1 2 e vertices of B blue.
• Colour the rest of the edges red.

The lower bound construction for the case \[n > \lceil \frac{m+n-1}{2} \rceil\] is a red \(K_{n-1,n-1}\).

The solution for the bipartite Ramsey tree vs star problem is broken into several lemmas. We first establish a general upper bound, which can be achieved in certain cases, and then we provide a solution for the rest of the cases.

The following lemma gives us the general upper bound for this problem.

Lemma 2.6. \[R_b(T_m, S_n) \leq n + \lfloor \frac{m-1}{2} \rfloor - 1\].

Proof. Consider a 2-colouring of Kb,b, where b = n + b m−1 2 c − 1. Let the independent sets of Kb,b be A and B. Number the vertices in each set from 1 to b. Consider a maximal blue Tk, k ≤ m − 1. W.l.o.g. say it is made by the first x vertices in A and the first k − x vertices of B. If k = 2b we get a red T2^b = T2(n+^b m−1 2 c−1) (i.e. at least a Tm), otherwise maximality forces a red Kb−x,k−^x (composed by the last b − x vertices of A and the first k − x vertices of B) and a red Kx,b+x−^k (composed by the first x vertices of A and the last b + x − k vertices of B) and so a red Sb−x+1, a red Sk−x+1, a red Sx+1 and a red Sb+x−k+1. The red Sb−x+1 and the red Sb+x−k+1 guarantee at least a red Sb−b ^m−^{1 c}+1 = Sn.

The above upper bound can be achieved in certain cases, as the next lemma shows.

Lemma 2.7. \[R_b(T_m, S_n) > n + \lfloor \frac{m-1}{2} \rfloor - 2\], if \((n + \lfloor \frac{m-1}{2} \rfloor - 2) = x \lfloor \frac{m-1}{2} \rfloor + y(m-1)\) where \(\{x, y\} \in \mathbb{Z}^*\).

Proof. Let b = n + b m−1 2 c − 2. Consider the following 2-colouring of Kb,b (see also Figure 4):

• Let the independent sets of \(K_{b,b}\) be A and B.
• Number the vertices in each set from 1 to b.
• Colour the edges joining the first \(\lfloor \frac{m-1}{2} \rfloor\) vertices of A with the first \(\lfloor \frac{m-1}{2} \rfloor\) vertices of B blue.
• Colour the edges joining the next \(\lceil \frac{m-1}{2} \rceil\) vertices of A with the next \(\lfloor \frac{m-1}{2} \rfloor\) vertices of B blue.
• Repeat colouring in this manner until we colour 2y sets.
• Colour the edges joining the next \(\lfloor \frac{m-1}{2} \rfloor\) vertices of A with the next \(\lfloor \frac{m-1}{2} \rfloor\) vertices of B blue.
• Repeat colouring in this manner until we reach the end of set A.
• Colour the rest of the edges red.

Figure 4: A 2 colouring of \(K_{6.6}\) without a blue (continuous line) \(T_4\) or a red (dashed line) \(S_7\)

The following theorem summarizes the above lemmas and provides us with the solution for the rest of the cases.

Theorem 2.5. \(R_b(T_m, S_n) = n + \lfloor \frac{m-1}{2} \rfloor - 1 - i\), where \(i \in \mathbb{Z}^*\) and \(\{y, x_0, \dots, x_i\} \in \mathbb{Z}^*\) such that i is minimum and \((n + \lfloor \frac{m-1}{2} \rfloor - 2 - i) = y(m-1) + \sum_{j=0}^{i} x_j (\lfloor \frac{m-1}{2} \rfloor - j)\).

Proof. If i=0 the theorem is an immediate consequence of Lemmas 2.6 and 2.7. The case of i=1 implies that \(n+\lfloor\frac{m-1}{2}\rfloor-2\) is not a sum of \(\lfloor\frac{m-1}{2}\rfloor\) and m-1 terms and we cannot use the same colouring as in Lemma 2.7. Any other colouring will lead to the creation of either a blue \(T_m\) or a red \(S_n\) and so \(R_b(T_m,S_n)\leq n+\lfloor\frac{m-1}{2}\rfloor-2-1\). Let \(n+\lfloor\frac{m-1}{2}\rfloor-2-i=y(m-1)+\sum_{j=0}^1x_j(\lfloor\frac{m-1}{2}\rfloor-j)\). The following colouring proves that \(R_b(T_m,S_n)>n+\lfloor\frac{m-1}{2}\rfloor-3\). Consider the following 2-colouring of \(K_{b,b}\), where \(b=n+\lfloor\frac{m-1}{2}\rfloor-3\):

• Let the independent sets of \(K_{b,b}\) be A and B.
• Number the vertices in each set from 1 to b.
• Colour the edges joining the first \(\lfloor \frac{m-1}{2} \rfloor\) vertices of A with the first \(\lceil \frac{m-1}{2} \rceil\) vertices of B blue.

• Colour the edges joining the next d m−1 2 e vertices of A with the next b m−1 2 c vertices of B blue.
• Repeat colouring in this manner until we colour 2y sets.
• Colour the edges joining the next b m−1 2 c vertices of A with the next b m−1 2 c vertices of B blue.
• Repeat colouring in this manner until we colour x⁰ sets.
• Colour the edges joining the next b m−1 2 c − 1 vertices of A with the next b m−1 2 c − 1 vertices of B blue.
• Repeat colouring in this manner until we colour x¹ sets.
• Colour the rest of the edges red.

Following similar arguments we can prove the statement for all possible values of i.

3. Conclusion

The bipartite Ramsey number Rb(H, G), where H and G are bipartite graphs, is the smallest integer p such that any blue-red colouring of the edges of the complete bipartite graph Kp,p forces the existence of a blue H or a red G. In this paper we have considered special cases of the bipartite Ramsey problem. More specifically, we investigated the existence of simpler monochromatic graphs such as stripes, stars and trees under a 2-colouring of the edges of a bipartite graph and we gave the Ramsey numbers for Rb(mP2, nP2), Rb(Tm, Tn), Rb(Sm, nP2), Rb(Tm, nP2) and Rb(Sm, Tn). Further research can be carried out to obtain better bounds for the general problem, to derive solutions for special cases or even to investigate the behaviour of small bipartite Ramsey numbers.

References

• [1] L. Beineke and A. Schwenk. On a bipartite form of the ramsey problem. In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pages 17–22, 1975.
• [2] W. Carnielli and E. Carmelo. k2,² − k1,n and k2,n − k2,n bipartite ramsey numbers. Discrete Mathematics, 223(1):83–92, 2000.
• [3] W. Carnielli and E. Monte Carmelo. On the ramsey problem for multicolor bipartite graphs. Advances in Applied Mathematics, 22(1):48–59, 1999.
• [4] Y. Caro and C. Rousseau. Asymptotic bounds for bipartite ramsey numbers. Journal of Combinatorics, 8(1):17–17, 2001.

• [5] F. Chung and R. Graham. On multicolor ramsey numbers for complete bipartite graphs. Journal of Combinatorial Theory, Series B, 18:164–169, 1975.
• [6] D. Conlon. A new upper bound for the bipartite ramsey problem. Journal of Graph Theory, 58(4):351–356, 2008.
• [7] L. Eroh and O. Oellermann. Bipartite rainbow ramsey numbers. Discrete Mathematics, 277(1):57–72, 2004.
• [8] G. Exoo. A bipartite ramsey number. Graphs and Combinatorics, 7(4):395–396, 1991.
• [9] R. Faudree and R. Schelp. Path-path ramsey-type numbers for the complete bipartite graph. Journal of Combinatorial Theory, Series B, 19(2):161–173, 1975.
• [10] W. Goddard, M. Henning, and O. Oellermann. Bipartite ramsey numbers and zarankiewicz numbers. Discrete Mathematics, 219:85–95, 2000.
• [11] A. Gyarf ´ as and J. Lehel. A ramsey-type problem in directed and bipartite graphs. ´ Periodica Mathematica Hungarica, 3(3):299–304, 1973.
• [12] J. Hattingh and M. Henning. Bipartite ramsey theory. Utilitas Mathematica, pages 217–230, 1998.
• [13] J. Hattingh and M. Henning. Star-path bipartite ramsey numbers. Discrete Mathematics, 185(1):255–258, 1998.
• [14] M. Henning and O. Oellermann. Bipartite ramsey theorems for multiple copies of k2,2. Utilitas Mathematica, pages 23–24, 1998.
• [15] R. Irving. A bipartite ramsey problem and the zarankiewicz numbers. Glasgow Mathematical Journal, 19(01):13–26, 1978.
• [16] Q. Lin and Y. Li. Bipartite ramsey numbers involving large kn,n. European Journal of Combinatorics, 30(4):923–928, 2009.
• [17] V. Longani. Some bipartite ramsey numbers. Southeast Asian Bulletin of Mathematics, 26(4):583–592, 2003.
• [18] S. Radziszowski. Small ramsey numbers. The Electronic Journal of Combinatorics, 1000(0):DS1–Aug, 2011.
• [19] F. Ramsey. On a problem of formal logic. Classic Papers in Combinatorics, pages 1–24, 1987.
• [20] V. Rosta. Ramsey theory applications. The Electronic Journal of Combinatorics, pages 1–43, 2004.

• [21] Z. Rui and S. Yongqi. The bipartite ramsey numbers b(c2m; k2,2). The Electronic Journal of Combinatorics, 18(P51):1, 2011.
• [22] A. Thomason. On finite ramsey numbers. European Journal of Combinatorics, 3:263–272, 1982.