# The $m$-bipartite Ramsey number $BR_{m}(H_{1},H_{2})$

Yaser Rowshan<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In a $(G^{1},G^{2})$ coloring of a graph $G$, every edge of $G$ is in $G^{1}$
or $G^{2}$. For two bipartite graphs $H_{1}$ and $H_{2}$, the bipartite Ramsey
number $BR(H_{1},H_{2})$ is the least integer $b\geq 1$, such that for every
$(G^{1},G^{2})$ coloring of the complete bipartite graph $K_{b,b}$, results in
either $H_{1}\subseteq G^{1}$ or $H_{2}\subseteq G^{2}$. As another view, for
bipartite graphs $H_{1}$ and $H_{2}$ and a positive integer $m$, the
$m$-bipartite Ramsey number $BR_{m}(H_{1},H_{2})$ of $H_{1}$ and $H_{2}$ is
the least integer $n$, such that every subgraph $G$ of $K_{m,n}$ results in
$H_{1}\subseteq G$ or $H_{2}\subseteq\overline{G}$. The size of $m$-bipartite
Ramsey number $BR_{m}(K_{2,2},K_{2,2})$, the size of $m$-bipartite Ramsey
number $BR_{m}(K_{2,2},K_{3,3})$ and the size of $m$-bipartite Ramsey number
$BR_{m}(K_{3,3},K_{3,3})$ have been computed in several articles up to now. In
this paper we determine the exact value of $BR_{m}(K_{2,2},K_{4,4})$ for each
$m\geq 2$.

###### Key words and phrases:

Ramsey numbers, Bipartite Ramsey numbers, complete graphs, m-bipartite Ramsey
number.

###### 2010 Mathematics Subject Classification:

05D10, 05C55.

##  1\. Introduction

In a $(G^{1},G^{2})$ coloring of a graph $G$, every edge of $G$ is in $G^{1}$
or $G^{2}$. For two graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the
smallest positive integer $n$, such that for every $(G^{1},G^{2})$ coloring of
the complete graph $K_{n}$, results in either $G\subseteq G^{1}$ or
$H\subseteq G^{2}$. Frank Harary always liked this notation! All such Ramsey
numbers $R(G,H)$ exist as well, for if $G$ has order $n$ and $H$ has order
$m$, then $R(G,H)\leq R(K_{n},K_{m})$. In [1], Beineke and Schwenk introduced
a bipartite version of Ramsey numbers. For given bipartite graphs $H_{1}$ and
$H_{2}$, the bipartite Ramsey number $BR(H_{1},H_{2})$ is defined as the
smallest positive integer $b$, such that any subgraph $G$ of $K_{b,b}$ results
in either a $H_{1}\subseteq G$ or $H_{2}\subseteq\overline{G}$. One can refer
to [8, 11, 14], [17, 4, 3, 15], [12, 22, 20, 9] , [10, 16, 18, 19] and their
references for further studies.

Suppose that $(G^{1},G^{2})$ be any $2$-edges coloring of $K_{m,n}$ when
$m\neq n$, also let $H_{1}$ and $H_{2}$ are two bipartite graphs, for each
$m\geq 1$, the $m$-bipartite Ramsey number $BR_{m}(H_{1},H_{2})$ of $H_{1}$
and $H_{2}$ is the least integer $n$, so that any $(G^{1},G^{2})$ coloring of
$K_{m,n}$ results in either a $H_{1}\subseteq G^{1}$ or $H_{2}\subseteq
G^{2}$. Z. Bi, G. Chartrand and P. Zhang in [2] evaluate
$BR_{m}(K_{2,2},K_{3,3})$ for each $m\geq 2$. Recently Y. Rowshan and M.
Gholami, by another simple proof, evaluated $BR_{m}(K_{2,2},K_{3,3})$ in [21].
Z. Bi, G. Chartrand, and P. Zhang in [5] evaluate $BR_{m}(K_{3,3},K_{3,3})$.

In this article we determine the exact value of $BR_{m}(K_{2,2},K_{4,4})$ for
each $m\geq 2$. In particular we prove the following theorem:

######  Theorem 1.1.

Let $m\geq 2$ be a positive integer. Then:

$BR_{m}(K_{2,2},K_{4,4})=\left\\{\begin{array}[]{ll}\text{does not
exist},&~{}~{}~{}if~{}~{}~{}m=2,3,4,\vspace{.2 cm}\\\
26&~{}~{}~{}if~{}~{}~{}m=5,\vspace{.2 cm}\\\
22&~{}~{}~{}if~{}~{}~{}m=6,7,\vspace{.2 cm}\\\
16&~{}~{}~{}if~{}~{}~{}m=8,\vspace{.2 cm}\\\
14&~{}~{}~{}if~{}~{}~{}m\in\\{9,10\ldots,13\\}.\vspace{.2 cm}\\\
\end{array}\right.$

There is a familiar problem corresponding to the Ramsey number
$R(K_{3},K_{3})$, which is stated as follows: What is the last number of
people who must be present at a meeting, where every two people are either
acquaintances or strangers, so that there are three among them who are either
mutual acquaintances or mutual strangers? Since $R(K_{3},K_{3})=6$, the answer
to this question is $6$. On the other hand, for a gathering of people, five of
whom are men, what is the smallest number of women who must also be present at
the meeting so that there are four among them, two men and two women, where
each man is an acquaintance of each woman, or there are eight among them, four
men and four women, where each man is a stranger of each woman. By Theorem
1.1, as $BR_{5}(K_{2,2},K_{4,4})=26$, the required number of women to be
present is $26$.

##  2\. Preparations

Suppose that $G=(V(G),E(G))$ is a graph. The degree of a vertex $v\in V(G)$ is
denoted by $\deg_{G}(v)$. For each $v\in V(G)$, $N_{G}(v)=\\{u\in
V(G),~{}~{}vu\in E(G)\\}$. The maximum and minimum degrees of $V(G)$ are
defined by $\Delta(G)$ and $\delta(G)$, respectively. Let $G[X,Y]$ (or in
short $[X,Y]$), be a bipartite graph with bipartition $X\cup Y$. Suppose that
$E(G[X^{\prime},Y^{\prime}])$, for short $E[X^{\prime},Y^{\prime}]$, denotes
the edge set of $G[X^{\prime},Y^{\prime}]$. We use $\Delta(G_{X})$ to denote
the maximum degree of vertices in part $X$ of $G$.

Let $(G^{1},G^{2})$ be a $2$-coloring of a graph $G$, then every edge of $G$
is in $G^{1}$ or $G^{2}$. For given graphs $G$, $H_{1}$, and $H_{2}$, we say
$G$ is $2$-colorable to $(H_{1},H_{2})$ if there exists a $2$-edge
decomposition of $G$, say $(G^{1},G^{2})$ where $H_{i}\nsubseteq G^{i}$ for
each $i=1,2$. We use $G\rightarrow(H_{1},H_{2})$, to show that $G$ is
$2$-colorable to $(H_{1},H_{2})$.

######  Definition 2.1.

The Zarankiewicz number $z((m_{1},m_{2}),K_{n_{1},n_{2}})$ is defined to be
the maximum number of edges in any subgraph $G$ of the complete bipartite
graph $K_{m_{1},m_{2}}$, such that $G$ does not contain $K_{n_{1},n_{2}}$.

######  Lemma 2.2.

([7])The following results on $z((m,n),K_{t,t})$ are true:

  * $\bullet$

$z((7,14),K_{2,2})\leq 31$.

  * $\bullet$

$z((7,16),K_{2,2})\leq 34$.

  * $\bullet$

$z((8,14),K_{2,2})\leq 35$.

  * $\bullet$

$z((8,16),K_{2,2})\leq 38$.

  * $\bullet$

$z((8,16),K_{4,4})\leq 90$.

  * $\bullet$

$z((9,14),K_{2,2})\leq 39$.

  * $\bullet$

$z((9,14),K_{4,4})\leq 88$.

  * $\bullet$

$z((10,14),K_{2,2})\leq 42$.

  * $\bullet$

$z((10,14),K_{4,4})\leq 97$.

###### Proof.

By using the bounds in Table $5$ of [7] and Table C.0 of [6], the proposition
holds. ∎

Hattingh and Henning in [13] prove that the next theorem:

######  Theorem 2.3.

[13] $BR(K_{2,2},K_{4,4})=14$.

######  Lemma 2.4.

Assume that $G$ be a subgraph of $K_{|X|,|Y|}$, where $|X|=m\geq 5$, and
$|Y|=n\geq 8$. If $\Delta(G_{X})\geq 8$, then either $K_{2,2}\subseteq G$ or
$K_{4,4}\subseteq\overline{G}$.

###### Proof.

Without loss of generality (W.l.g), let $\Delta(G_{X})=8$ and
$N_{G}(x)=Y^{\prime}$, where $|Y^{\prime}|\geq=8$. Suppose that
$K_{2,2}\nsubseteq G$, hence $|N_{G}(x^{\prime})\cap Y^{\prime}|\leq 1$ for
any $x^{\prime}\in X\setminus\\{x\\}$. So, since $|X|\geq 5$ and
$|Y^{\prime}|=8$, then it is easy to check that
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x\\},Y^{\prime}]$. ∎

######  Lemma 2.5.

Let $G$ be a subgraph of $K_{|X|,|Y|}$, where $|X|=m\geq 9$, and $|Y|=n\geq
9$. If $\Delta(G_{X})\geq 7$, then either $K_{2,2}\subseteq G$ or
$K_{4,4}\subseteq\overline{G}$.

###### Proof.

W.l.g let $N_{G}(x)=Y^{\prime}$, where $|Y^{\prime}|=7$. Suppose that
$K_{2,2}\nsubseteq G$. Since $|X|\geq 9$ and $|Y^{\prime}|=7$, if
$|N_{G}(x^{\prime})\cap Y^{\prime}|=0$ for some $x^{\prime}\in
X\setminus\\{x\\}$ then by pigeon-hole principle one can check that
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x\\},Y^{\prime}]$. So suppose that
$|N_{G}(x^{\prime})\cap Y^{\prime}|=1$ for each $x^{\prime}\in
X\setminus\\{x\\}$. Therefore as $|X|\geq 9$ and $|Y^{\prime}|=7$ it is easy
to say that there exists two vertices of $X\setminus\\{x\\}$ say
$x^{\prime},x^{\prime\prime}$, such that $N_{G}(x^{\prime})\cap
Y^{\prime}=N_{G}(x^{\prime\prime})\cap Y^{\prime}$. Let $N_{G}(x^{\prime})\cap
Y^{\prime}=N_{G}(x^{\prime\prime})\cap Y^{\prime}=\\{y^{\prime}\\}$. Hence by
pigeon-hole principle one can check that
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x\\},Y^{\prime}\setminus\\{y^{\prime}\\}]$.
Hence lemma holds. ∎

##  3\. Proof of the main results

In this section, we prove Theorem 1.1. To simplify the comprehension, let us
split the proof of Theorem 1.1 into small parts. We begin with the following
result:

######  Theorem 3.1.

$BR_{5}(K_{2,2},K_{4,4})=26$.

###### Proof.

Suppose that
$(X=\\{x_{1},x_{2},x_{3},x_{5}\\},Y=\\{y_{1},y_{2},\ldots,y_{25}\\})$ be the
partition sets of $K=K_{5,25}$ and $G$ be a subgraph of $K$, such that for
each $x\in X$, $N_{G}(x)$ is defined as follow:

  * •

(A1): $N_{G}(x_{1})=\\{y_{1},y_{2},\ldots,y_{7}\\}$.

  * •

(A2): $N_{G}(x_{2})=\\{y_{1},y_{8},y_{9}\ldots,y_{13}\\}$.

  * •

(A3): $N_{G}(x_{3})=\\{y_{2},y_{8},y_{14},y_{15}\ldots,y_{18}\\}$.

  * •

(A4): $N_{G}(x_{4})=\\{y_{3},y_{9},y_{14},y_{19},\ldots,y_{22}\\}$.

  * •

(A5): $N_{G}(x_{5})=\\{y_{4},y_{10},y_{15},y_{19},y_{23},y_{24},y_{25}\\}$.

Now for each $i,j\in\\{1,\ldots,5\\}$, by $(Ai)$ and $(Aj)$, it can be said
that $|N_{G}(x_{i})\cap N_{G}(x_{j})|=1$, which means that $K_{2,2}\nsubseteq
G$. Also, for each $i\in\\{1,2\ldots,5\\}$, it is easy to check that
$|\cup_{j=1,j\neq i}^{j=5}N_{G}(x_{j})|=22$. Therefore,
$K_{4,4}\nsubseteq\overline{G}[X\setminus\\{x_{i}\\},Y]$ for each $x_{i}\in
X$, which means that $BR_{5}(K_{2,2},K_{4,4})\geq 26$.

Now assume that
$(X=\\{x_{1},x_{2},x_{3},x_{5}\\},Y=\\{y_{1},y_{2},\ldots,y_{26}\\})$ be the
partition sets of $K_{5,26}$ and let $G$ be a subgraph of $K_{5,26}$, such
that $K_{2,2}\nsubseteq G$. Consider $\Delta=\Delta(G_{X})$. Since
$K_{2,2}\nsubseteq G$, if $\Delta\geq 8$, then by Lemma 2.4, the proof is
complete. Also, since $|Y|=26$, if $\Delta\leq 5$, then it is easy to check
that $K_{4,4}\subseteq\overline{G}$. Therefore let $\Delta\in\\{6,7\\}$. Now
we verify the next claim.

######  Claim 3.2.

If $\Delta=7$, then we have $K_{4,4}\subseteq\overline{G}$.

###### Proof of Claim 3.2.

W.l.g let $\Delta=\deg_{G}(x_{1})$ and
$N_{G}(x_{1})=Y_{1}=\\{y_{1},\ldots,y_{7}\\}$. Since $K_{2,2}\nsubseteq G$, so
$|N_{G}(x_{i})\cap Y_{1}|\leq 1$ and $N_{G}(x_{i})\cap Y_{1}\neq
N_{G}(x_{j})\cap Y_{1}$ for any $i,j\in\\{2,3,4,5\\}$, otherwise
$K_{4,4}\subseteq\overline{G}[X,Y_{1}]$. Suppose that there exists a vertex of
$X\setminus\\{x_{1}\\}$, so that $|N_{G}(x)|=6$, and w.l.g suppose that
$x=x_{2}$ and $N_{G}(x_{2})=Y_{2}=\\{y_{1},y_{8}\ldots,y_{12}\\}$. Therefore,
since $K_{2,2}\nsubseteq G$, we have $|N_{G}(x_{i})\cap
Y_{2}\setminus\\{y_{1}\\}|\leq 1$, also one can checked that
$|N_{G}(x_{i})\cap Y_{2}\setminus\\{y_{1}\\}|=1$ for at least two
$i\in\\{3,4,5\\}$, otherwise
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{2}\\},Y_{2}\setminus\\{y_{1}\\}]$.
W.l.g assume that $|N_{G}(x_{i})\cap Y_{2}\setminus\\{y_{1}\\}|=1$ for
$i=3,4$. So, as $\Delta=7$, $|N_{G}(x_{i})\cap(Y_{1}\cup Y_{2})|=2$, one can
say that $|N_{G}(x_{i})\cap Y\setminus(Y_{1}\cup Y_{2})|\leq 5$, therefore
$|\cup_{j=1}^{j=4}N_{G}(x_{j})|\leq 22$, which means that
$K_{4,4}\subseteq\overline{G}$.

Now let $|N_{G}(x)|=7$ for each $x\in X$. Suppose that $N_{G}(x_{i})=Y_{i}$
for each $i\in\\{1,2,\ldots,5\\}$. Hence Since $K_{2,2}\nsubseteq G$, one can
say that $|N_{G}(x_{i})\cap Y_{j}|=1$ and $N_{G}(x_{i})\cap Y_{j}\neq
N_{G}(x_{l})\cap Y_{j}$ for each $i,l,j\in\\{1,2,3,4,5\\}$ where $i\neq j\neq
l\neq i$, otherwise $K_{4,4}\subseteq\overline{G}[X,Y]$. Therefore it is easy
to say that $|\cup_{j=1,j\neq i}^{j=5}N_{G}(x_{j})|=22$. Hence as $|Y|=26$ for
each $x\in X$ we have $K_{4,4}\subseteq\overline{G}[X\setminus\\{x\\},Y]$. So,
claim holds. ∎

Hence, we may assume that $\Delta=6$. W.l.g let $N_{G}(x_{1})=Y_{1}$. Since
$K_{2,2}\nsubseteq G$, thus $|N_{G}(x_{i})\cap Y_{1}|\leq 1$ for each
$i\in\\{2,3,4,5\\}$. Also, we may suppose that $|N_{G}(x_{i})\cap Y_{1}|=1$
for at least three vertices of $X\setminus\\{x_{1}\\}$, otherwise
$K_{4,4}\subseteq\overline{G}[X,Y_{1}]$. Now, w.l.g let $X_{1}=\\{x\in
X\setminus\\{x_{1}\\},~{}~{}|N_{G}(x_{i})\cap Y_{1}|=1\\}$. As $|Y|=26$,
$|X_{1}|\geq 3$, and $\Delta=6$, one can check that $|\cup_{x\in
X_{1}\cup\\{x_{1}\\}}N_{G}(x)|\leq 21$, which means that
$K_{4,4}\subseteq\overline{G}$. Hence we have $BR_{5}(K_{2,2},K_{4,4})=26$.

∎

In the following theorem, we compute the size of $BR_{m}(K_{2,2},K_{4,4})$ for
$m=6,7$.

######  Theorem 3.3.

$BR_{6}(K_{2,2},K_{4,4})=BR_{7}(K_{2,2},K_{4,4})=22$.

###### Proof.

It suffices to show that :

  * •

(I): $K_{7,21}\rightarrow(K_{2,2},K_{4,4})$.

  * •

(II): $BR_{6}(K_{2,2},K_{4,4})\leq 22$.

We begin with $(I)$. Let
$(X=\\{x_{1},\ldots,x_{7}\\},Y=\\{y_{1},\ldots,y_{21}\\})$ be the partition
sets of $K=K_{7,21}$ and let $G$ be a subgraph of $K$, such that for each
$x\in X$ we define $N_{G}(x)$ as follow:

  * •

(D1): $N_{G}(x_{1})=\\{y_{1},y_{2},y_{3},y_{4},y_{5},y_{6}\\}$.

  * •

(D2): $N_{G}(x_{2})=\\{y_{1},y_{7},y_{8},y_{9},y_{10},y_{11}\\}$.

  * •

(D3): $N_{G}(x_{3})=\\{y_{2},y_{7},y_{12},y_{13},y_{14},y_{15}\\}$.

  * •

(D4): $N_{G}(x_{4})=\\{y_{3},y_{8},y_{12},y_{16},y_{17},y_{18}\\}$.

  * •

(D5): $N_{G}(x_{5})=\\{y_{4},y_{9},y_{13},y_{16},y_{19},y_{20}\\}$.

  * •

(D6): $N_{G}(x_{6})=\\{y_{5},y_{10},y_{14},y_{17},y_{19},y_{21}\\}$.

  * •

(D7): $N_{G}(x_{7})=\\{y_{6},y_{11},y_{15},y_{18},y_{20},y_{21}\\}$.

Now, for each $i,j\in\\{1,2,\ldots,7\\}$ by $(Di)$ and $(Dj)$ it can be said
that:

  * •

(E1): $|N_{G}(x_{i})\cap N_{G}(x_{j})|=1$ for each $i,j\in\\{1,2,\ldots,7\\}$.

  * •

(E2): $|\cup_{i=1}^{i=4}N_{G}(x_{j_{i}})|=18$ for each
$j_{1},j_{2},j_{3},j_{4}\in\\{1,\ldots,7\\}$.

By $(E1)$, one can say that $K_{2,2}\nsubseteq G$. Also by $(E2)$, it is easy
to say that $K_{4,4}\nsubseteq\overline{G}$ which means that
$K_{7,21}\rightarrow(K_{2,2},K_{4,4})$, that is the part $(I)$ is correct.

Now we show that $(II)$ is established, that is, we show that for any subgraph
of $K_{6,22}$ say $G$, either $K_{2,2}\subseteq G$ or
$K_{4,4}\subseteq\overline{G}$. Let
$(X=\\{x_{1},x_{2},\ldots,x_{6}\\},Y=\\{y_{1},y_{2},\ldots,y_{22}\\})$ be the
partition sets of $K=K_{6,22}$ and $G$ be a subgraph of $K$, where
$K_{2,2}\nsubseteq G$. We show that $K_{4,4}\subseteq\overline{G}$. Consider
$\Delta=\Delta(G_{X})$. Since $K_{2,2}\nsubseteq G$, by Lemma 2.4, $\Delta\leq
7$. Now we verify the following claim.

######  Claim 3.4.

If $\Delta=7$, then $K_{4,4}\subseteq\overline{G}$.

###### Proof of Claim 3.4.

W.l.g let $|N_{G}(x_{1})=Y_{1}|=7$. Since $K_{2,2}\nsubseteq G$ for each
$i,j\in\\{2,\ldots,6\\}$, we have $|N_{G}(x_{i})\cap Y_{1}|\leq 1$ and
$N_{G}(x_{i})\cap Y_{1}\neq N_{G}(x_{j})\cap Y_{1}$ , otherwise since
$|Y_{1}|=7$, it is easy to check that $K_{4,4}\subseteq\overline{G}[X,Y_{1}]$.
Therefore as $|X|=6$ and $|Y_{1}|=7$, for each $x\neq x_{1}$ it can be said
that $K_{4,3}\subseteq\overline{G}[X\setminus\\{x_{1},x\\},Y_{1}]$. So, as
$|Y|=22$, if there exists a vertex of $Y\setminus Y_{1}$, so that
$|N_{\overline{G}}(y)\cap(X\setminus\\{x_{1}\\})|\geq 4$, then
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}\cup\\{y\\}]$. Hence
assume that $|N_{G}(y)\cap(X\setminus\\{x_{1}\\})|\geq 2$ for each $y\in
Y\setminus Y_{1}$, that is $|E(G[X,Y\setminus Y_{1}])|\geq 30$. Therefore by
pigeon-hole principle, one can check that there exist at least one vertices of
$X\setminus\\{x_{1}\\}$ say $x_{2}$, such that $|N_{G}(x_{2})\cap(Y\setminus
Y_{1})|\geq 5$. Suppose that $N_{G}(x_{2})\cap(Y\setminus Y_{1})=Y_{2}$. So as
$K_{2,2}\nsubseteq G$, $|N_{G}(x_{i})\cap Y_{2}|\leq 1$ for each
$i\in\\{3,4,5,6\\}$. Therefore as $|Y_{2}|\geq 5$, we have
$K_{4,1}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{2}]$. Hence as
$K_{4,3}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}]$, it can be
said that, $K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}\cup
Y_{2}]$. Hence claim holds. ∎

Therefore, by Claim 3.4 assume that $\Delta\leq 6$. Let $\Delta=5$ and w.l.g
suppose that $\Delta=|N_{G}(x_{1})|$. Since $K_{2,2}\nsubseteq G$, thus
$|N_{G}(x_{i})\cap N_{G}(x_{1})|=1$ for at least three vertices of
$X\setminus\\{x_{1}\\}$ say $x_{2},x_{3},x_{4}$, otherwise
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}]$. Hence, as
$\Delta=5$, one can check that $|\cup_{i=1}^{i=4}Y_{i}|\leq 17$, where
$Y_{i}=N_{G}(x_{i})$. So, since $|Y|=22$, we have
$K_{4,4}\subseteq\overline{G}$.

So let $\Delta=6$. W.l.g let $\Delta=\deg_{G}(x_{1})$ and
$N_{G}(x_{1})=Y_{1}$. Since $K_{2,2}\nsubseteq G$, thus $|N_{G}(x_{i})\cap
Y_{1}|\leq 1$ for each $i\in\\{2,3,4,5,6\\}$. Now we verify the following
claim.

######  Claim 3.5.

$|N_{G}(x_{i})\cap Y_{1}|=1$ and $N_{G}(x_{i})\cap Y_{1}\neq N_{G}(x_{j})\cap
Y_{1}$ for each $i,j\in\\{2,3,4,5,6\\}$.

###### Proof of Claim 3.5.

By contradiction, w.l.g assume that $|N_{G}(x_{2})\cap Y_{1}|=0$. Therefore,
$|N_{G}(x_{i})\cap Y_{1}|=1$ and $N_{G}(x_{i})\cap Y_{i}\neq N_{G}(x_{j})\cap
Y_{i}$ for each $i,j\in\\{3,4,5,6\\}$, otherwise
$K_{4,4}\subseteq\overline{G}[X,Y_{1}]$. Now as $|X|=|Y_{1}|=6$, it can be
said that $K_{4,2}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}]$.
If $|N_{G}(x_{2})|=6$ then
$K_{4,2}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},N_{G}(x_{2})]$,
hence $K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}\cup
N_{G}(x_{2})]$. So suppose that $|N_{G}(x_{2})|\leq 5$. If $|N_{G}(x_{2})|\leq
3$ then as $|Y|=22$ it is clear that $K_{4,4}\subseteq\overline{G}$. Hence we
may suppose that $4\leq|N_{G}(x_{2})|\leq 5$. If $|N_{G}(x_{2})|=4$, then
there exist at least two vertices of $X\setminus\\{x_{1},x_{2}\\}$ say
$x^{\prime},x^{\prime\prime}$, such that $|N_{G}(x_{2})\cap N_{G}(x)|=1$ for
each $x\in\\{x^{\prime},x^{\prime\prime}\\}$, otherwise
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{2}\\},N_{G}(x_{2})]$. W.l.g
assume that $x^{\prime}=x_{3},x^{\prime\prime}=x_{4}$. Hence as $\Delta=6$,
$|N_{G}(x_{2})|=4$, and $|N_{G}(x_{i})\cap N_{G}(x_{j})|=1$ for each
$i\in\\{1,2\\}$ and $j\in\\{3,4\\}$, one can check that
$|\cup_{j=1}^{j=4}N_{G}(x_{j})|\leq 18$, which means that
$K_{4,4}\subseteq\overline{G}$. So suppose that $|N_{G}(x_{2})|=5$, hence for
at least three vertices of $X\setminus\\{x_{1},x_{2}\\}$ say
$\\{x_{3},x_{4},x_{5}\\}$, we have $|N_{G}(x_{2})\cap N_{G}(x_{i})|=1$,
otherwise $K_{4,4}\subseteq\overline{G}$. If $|N_{G}(x_{i})|\leq 5$ for at
least one vertex of $\\{x_{3},x_{4},x_{5}\\}$, then as $\Delta=6$,
$|N_{G}(x_{2})|=5$, and $|N_{G}(x_{i})\cap N_{G}(x_{j})|=1$ for each
$i\in\\{1,2\\}$ and each $j\in\\{3,4\\}$, one can say that
$|\cup_{j=1}^{j=4}N_{G}(x_{j})|\leq 18$, which means that
$K_{4,4}\subseteq\overline{G}$. So suppose that $|N_{G}(x_{i})|=6$, for each
$x\in\\{x_{3},x_{4},x_{5}\\}$. Consider $N_{G}(x_{3})$, hence there is at
least one vertex of $\\{x_{4},x_{5}\\}$ say $x$, such that $|N_{G}(x_{3})\cap
N_{G}(x_{2})\cap(Y\setminus(Y_{1}\cup Y_{2}))|=1$ where $Y_{i}=N_{G}(y_{i})$,
otherwise $K_{4,4}\subseteq\overline{G}$. Therefore
$|N_{G}(x_{3})\cap(Y\setminus(Y_{1}\cup Y_{2}\cup Y_{3}))|=3$, which means
that $|\cup_{j=1}^{j=4}N_{G}(x_{j})|=18$. Therefore, it is easy to say that
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{5},x_{6}\\},(Y\setminus(Y_{1}\cup
Y_{2}\cup Y_{3}\cup Y_{4}))]$. For the case that there exists
$i,j\in\\{2,3,\ldots,6\\}$ such that $N_{G}(x_{i})\cap Y_{1}=N_{G}(x_{j})\cap
Y_{1}$ the proof is same. ∎

Hence by Claim 3.5, w.l.g we may suppose that $Y_{1}=\\{y_{1},\ldots,y_{6}\\}$
and let $x_{i}y_{i-1}\in E(G)$ for $i=2,\ldots,6$. Now we verify the following
claim.

######  Claim 3.6.

$|N_{G}(x_{i})|=6=\Delta$ for each $i\in\\{2,3,4,5,6\\}$.

###### Proof of Claim 3.6.

By contradiction, assume that $|N_{G}(x_{2})|\leq 5$, that is
$|N_{G}(x_{2})\cap(Y\setminus Y_{1})|\leq 4$. W.l.g assume that
$N_{G}(x_{2})\cap(Y\setminus Y_{1})=Y_{2}$. Since $|X|=6$, one can say that
there is at least two vertices of $X\setminus\\{x_{1},x_{2}\\}$ say
$x_{3},x_{4}$, such that $|N_{G}(x_{i})\cap Y_{2}|=1$, for $i=2,3$, otherwise
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{2}\\},Y_{2}]$. Hence as
$\Delta=6$, one can check that $|\cup_{i=1}^{i=4}Y_{i}|\leq 18$, where
$Y_{i}=N_{G}(x_{i})$. So as and $|Y|=22$, we have
$K_{4,4}\subseteq\overline{G}[\\{x_{1},x_{2},x_{3},x_{4}\\},Y\setminus\cup_{i=1}^{i=4}Y_{i}]$
∎

Therefore by Claims 3.5 and 3.6, it can be said that
$|\cup_{i=1}^{i=6}Y_{i}|=21$, that is there exists one vertex of $Y$, say
$y_{22}$, such that $K_{6,1}\subseteq\overline{G}[X,\\{y_{22}\\}]$. Suppose
that $Y_{i}=N_{G}(x_{i})$ for $i=1,2$, and w.l.g assume that
$Y_{1}=\\{y_{1},\ldots,y_{6}\\}$ and $Y_{2}=\\{y_{1},y_{7},\ldots y_{11}\\}$.
Hence by Claims 3.5 and 3.6 it is easy to say that there exists one vertex of
$Y_{1}\setminus\\{y_{1}\\}$ say $y^{\prime}$ and one vertex of
$Y_{2}\setminus\\{y_{1}\\}$ say $y^{\prime\prime}$ such that
$K_{4,2}\subseteq\overline{G}[\\{x_{3},\ldots,x_{6}\\},\\{y^{\prime},y^{\prime\prime}\\}]$.
Hence one can check that
$K_{4,4}\subseteq\overline{G}[\\{x_{3},\ldots,x_{6}\\},\\{y_{1},y^{\prime},y^{\prime\prime},y_{22}\\}]$.

Thus, for any subgraph of $K_{6,22}$ say $G$, either $K_{2,2}\subseteq G$ or
$K_{4,4}\subseteq\overline{G}$. Hence, $BR_{6}(K_{2,2},K_{4,4})\leq 22$ and so
by $(I)$, $BR_{6}(K_{2,2},K_{4,4})=22$. This also implies that for any
subgraph of $K_{7,22}$ say $G$, either $K_{2,2}\subseteq G$ or
$K_{4,4}\subseteq\overline{G}$. Therefore, by $(I)$,
$BR_{7}(K_{2,2},K_{4,4})=22$. Hence theorem holds.

∎

Let $G$ be a subgraph of $K_{|X|,|Y|}=K_{m,n}$ where
$X=\\{x_{1},\ldots,x_{m}\\}$ and $Y=\\{y_{1},\ldots,y_{n}\\}$ are the
partition of $K_{|X|,|Y|}$. For any subgraph $G$ of $K_{m,n}$ suppose that
$A[G]=[a_{ij}]$ be an $m\times n$ matrix, where for each $i\in[m]$ and each
$j\in[n]$, $a_{ij}=1$ if the edges $x_{i}y_{j}\in E(G)$, and $a_{ij}=0$ if the
edges $x_{i}y_{j}\in E(\overline{G})$. The matrix $A[G]=[a_{ij}]$ represents a
$2$-coloured $K_{m,n}$. In the next two theorems, we find the value of
$BR_{8}(K_{2,2},K_{4,4})$, by considering a particular $2$-coloured of
$K_{8,15}$ and a $2$-coloured of $K_{8,16}$.

######  Theorem 3.7.

$K_{8,15}\rightarrow(K_{2,2},K_{4,4})$.

###### Proof.

Let $G$ be a subgraph of $K_{8,15}$ such that $A[G]$ is shown in the following
matrix:

$A[G]=A_{8\times 15}=\begin{bmatrix}1&1&1&1&0&0&0&0\\\ 1&0&0&0&1&0&1&0\\\
1&0&0&0&0&1&0&1\\\ 1&0&0&0&0&0&0&0\\\ 0&1&0&0&1&0&0&0\\\ 0&1&0&0&0&1&1&0\\\
0&1&0&0&0&0&0&1\\\ 0&0&1&0&1&0&0&0\\\ 0&0&1&0&0&1&0&0\\\ 0&0&1&0&0&0&1&0\\\
0&0&0&1&1&0&0&1\\\ 0&0&0&1&0&1&0&0\\\ 0&0&0&1&0&0&1&0\\\ 0&0&0&0&1&1&0&0\\\
0&0&0&0&0&0&1&1\\\ \end{bmatrix}$

Set $X_{1}=\\{x_{1},x_{2},x_{3},x_{4}\\}$ and $X_{2}=X\setminus X_{1}$.
Therefore by matrix $A[G]$ it can be said that the following items are true:

  * •

(P1): $|N_{G}(x_{i})\cap N_{G}(x_{j})|=1$ for each $i,j\in\\{1,\ldots,8\\}$.

  * •

(P2): $|N_{G}(x_{i})|=4$ for each $x\in X_{1}$.

  * •

(P3): $|N_{G}(x_{i})|=5$ for each $x\in X_{2}$.

  * •

(P4): $|\cup_{i=1}^{i=4}N_{G}(x_{i})|=13$.

  * •

(P5): $|\cup_{i=5}^{i=8}N_{G}(x_{i})|=14$.

Therefore by $(P1)$ we have $G$ is $K_{2,2}$-free, also by $(P4)$ and $(P6)$,
for $i=1,2$ it can be said that $K_{4,4}\nsubseteq\overline{G}[X_{i},Y]$. Also
by $A[G]$ it can be said that the following items are true:

  * •

(M1): $|N_{G}(x_{i})\cup N_{G}(x_{j})|=7$ for each $x_{i},x_{j}\in X_{1}$.

  * •

(M2): $|N_{G}(x_{i})\cup N_{G}(x_{j})\cup N_{G}(x_{l})|=10$ for each
$x_{i},x_{j},x_{l}\in X_{1}$.

  * •

(M3): $|N_{G}(x_{i})\cup N_{G}(x_{j})|=9$ for each $x_{i},x_{j}\in X_{2}$.

  * •

(M4): $|N_{G}(x_{i})\cup N_{G}(x_{j})\cup N_{G}(x_{l})|=12$ for each
$x_{i},x_{j},x_{l}\in X_{2}$.

Now we verify the following claim.

######  Claim 3.8.

$\overline{G}$ is $K_{4,4}$-free.

###### Proof of Claim 3.8.

By contradiction, suppose that $K$ is a copy of $K_{4,4}$ in $\overline{G}$,
also assume that $V(K)\cap X=\\{w_{1},w_{2},w_{3},w_{4}\\}=W$ and $V(K)\cap
Y=\\{w^{\prime}_{1},w^{\prime}_{2},w^{\prime}_{3},w^{\prime}_{4}\\}=W^{\prime}$.
Since $K_{4,4}\subseteq\overline{G}[W,W^{\prime}]$, then by $(P4)$ and $(M4)$,
one can say that $1\leq|W\cap X_{2}|\leq 2$. Assume that $|W\cap X_{i}|=2$.
W.l.g let $w_{1},w_{2}\in X_{1}$ and $w_{3},w_{4}\in X_{2}$. Hence, by $(M1)$,
we have $|N_{G}(w_{1})\cup N_{G}(w_{2})|=7$. Now consider $w_{3},w_{4}$, as
$|N_{G}(w_{i})\cap N_{G}(w_{j})|=1$ for each $i,j\in\\{1,\ldots,8\\}$, and
$y_{1}\notin N_{G}(x)$ for each $x\in X_{2}$ one can say that
$|N_{G}(w_{1})\cup N_{G}(w_{2})\cup N_{G}(w_{i})|=10$ for each
$i\in\\{3,4\\}$. Also, as $|N_{G}(w_{i})\cap N_{G}(w_{j})|=1$, it is easy to
check that $|N_{G}(w_{1})\cup N_{G}(w_{2})\cup N_{G}(w_{3})\cup
N_{G}(w_{4})|\geq 12$, which means that $K_{4,4}\nsubseteq\overline{G}[W,Y]$,
a contradiction. So assume that $|W\cap X_{1}|=3$, and w.l.g let $w_{4}\in
X_{2}$. Hence, by $(P1)$, $(P3)$, and $(M2)$, one can say that
$|N_{G}(w_{1})\cup N_{G}(w_{2})\cup N_{G}(w_{3})\cup N_{G}(w_{4})|=12$, which
means that $K_{4,4}\nsubseteq\overline{G}[W,Y]$, a contradiction again. Hence
claim holds. ∎

Therefore by $(P1)$ and by Claim 3.8, we have the proof of the theorem is
complete. ∎

To proving the next theorem, we need to establish the following lemma.

######  Lemma 3.9.

([7])The following results on $z((m,n),K_{t,t})$ are true:

  * $\bullet$

$z((6,9),K_{2,2})\leq 21$.

  * $\bullet$

$z((6,12),K_{2,2})\leq 26$.

  * $\bullet$

$z((5,6),K_{2,2})\leq 14$.

  * $\bullet$

$z((7,9),K_{2,2})\leq 24$.

  * $\bullet$

$z((7,12),K_{2,2})\leq 28$.

  * $\bullet$

$z((7,16),K_{2,2})\leq 34$.

###### Proof.

By using the bounds in Table $5$ of [7] and Table C.4 of [6], the proposition
holds. ∎

######  Theorem 3.10.

$BR_{8}(K_{2,2},K_{4,4})=16$.

###### Proof.

Let $G$ be any subgraph of $K_{8,16}$. Since $|E(K_{8,16})|=128$, then we may
assume that $|E(G)|=38$ and $|E(\overline{G})|=90$, otherwise by Lemma 2.2 as
$z((8,16),K_{2,2})\leq 38$ and $z((8,16),K_{4,4})\leq 90$ it can be said that
either $K_{2,2}\subseteq G$ or $K_{4,4}\subseteq\overline{G}$, that is the
proof is complete. Now let $|E(G)|=38$, $|E(\overline{G})|=90$ and w.l.g
assume that $K_{2,2}\nsubseteq G$. Since $z((7,16),K_{2,2})\leq 34$, if there
exist a vertex of $G$ say $x$, such that $|N_{G}(x)|\leq 3$, then it is easy
to say that $|E(G\setminus\\{x\\})|\geq 35$. Therefore, we have
$K_{2,2}\nsubseteq G$, a contradiction. Hence, $\delta(G)=4$. Define
$X^{\prime}$ as follow:

$X^{\prime}=\\{x\in X,~{}~{}\deg_{G}(x)=4\\}$

Since $|E(G)|=38$ and $|X|=8$, it is clear that $|X^{\prime}|\geq 2$. By
considering $X^{\prime}$, we verify the following claim.

######  Claim 3.11.

If there exist two members of $X^{\prime}$, say $x,x^{\prime}$ such that
$|N_{G}(x)\cap N_{G}(x^{\prime})|=1$, then $K_{4,4}\subseteq\overline{G}$.

###### Proof of Claim 3.11.

W.l.g let $x=x_{1},x^{\prime}=x_{2}$,
$N_{G}(x_{1})=Y_{1}=\\{y_{1},y_{2},y_{3},y_{4}\\}$ and
$N_{G}(x_{2})=Y_{2}=\\{y_{1},y_{5},y_{6},y_{7}\\}$. Now set
$Y^{\prime}=Y_{1}\cup Y_{2}$. Hence we have the following fact.

  * •

(F1): There is at least one member of $X_{1}=X\setminus\\{x_{1},x_{2}\\}$ say
$x$, such that $|N_{G}(x)\cap Y^{\prime}|=2$.

To proving $(F1)$, by contrary, let $|N_{G}(x)\cap Y^{\prime}|\leq 1$ for each
$x\in X_{1}$. Set $X_{1}=X\setminus\\{x_{1},x_{2}\\}$ and
$Y^{\prime}=Y\setminus(Y_{1}\cup Y_{2})$, therefore we have
$|E(G[X_{1},Y^{\prime}])|\geq 25$. Hence by Lemma 3.9 as $z((6,9),K_{2,2})\leq
24$, we have $K_{2,2}\subseteq G$, a contradiction. Hence The Fact $(F1)$ is
correct.

Therefore, by $(F1)$ w.l.g let $|N_{G}(x_{3})\cap Y^{\prime}|=2$ and
$Y_{3}=\\{y_{2},y_{5},y_{8},y_{9}\\}\subseteq N_{G}(x_{3})$. If $x_{3}\in
X^{\prime}$, then by an argument similar to the proof of $(F1)$, one can check
that there exists at least one member of $X\setminus\\{x_{1},x_{2},x_{3}\\}$
say $x$, such that $|N_{G}(x)|\leq 5$ and $|N_{G}(x)\cap(Y^{\prime}\cup
Y_{3})|\geq 2$. Therefore, $|N_{G}(x)\cap Y\setminus(Y^{\prime}\cup
Y_{3})|\leq 3$, hence it is easy to say that
$K_{4,4}\subseteq\overline{G}[\\{x_{1},x_{2},x_{3},x\\},Y\setminus(Y^{\prime}\cup
Y_{3})]$. So, suppose that $|N_{G}(x_{3})|\geq 5$. Now we verify the following
two cases.

Case 1: $|N_{G}(x_{3})|=5$. In this case, we have the following fact.

  * •

(F2): There exists one member of $X\setminus\\{x_{1},x_{2},x_{3}\\}$ say $x$,
such that $|N_{G}(x)|=5$ and $|N_{G}(x)\cap(Y^{\prime}\cup Y_{3})|=3$.

For prove $(F2)$, by contrary, let $|N_{G}(x)\cap(Y^{\prime}\cup Y_{3})|\leq
2$ for each $X\setminus\\{x_{1},x_{2},x_{3}\\}$. Set
$X_{1}=X\setminus\\{x_{1},x_{2},x_{3}\\}$ and
$Y^{\prime\prime}=Y\setminus(Y^{\prime}\cup Y_{3})$, therefore we have
$|E(G[X_{1},Y^{\prime\prime}])|\geq 15$. Hence by Lemma 3.9 as
$z((5,6),K_{2,2})\leq 14$ we have $K_{2,2}\subseteq G$, a contradiction. Hence
The Fact $(F2)$ is true.

Therefore, by $(F2)$ w.l.g let $|N_{G}(x_{4})\cap Y\setminus(Y^{\prime}\cup
Y_{3}\cup Y^{\prime\prime})|=3$ and let
$Y_{4}=\\{y^{\prime},y^{\prime\prime},y^{\prime\prime},y_{10},y_{12}\\}\subseteq
N_{G}(x_{4})$. If $|N_{G}(x_{4})|\leq 5$, then it is easy to say that
$K_{4,4}\subseteq\overline{G}[\\{x_{1},x_{2},x_{3},x_{4}\\},Y\setminus(Y^{\prime}\cup
Y_{3}\cup Y_{4})]$. So suppose that $|N_{G}(x_{4})|=6$ and assume that
$Y_{4}=\\{y^{\prime},y^{\prime\prime},y^{\prime\prime\prime},y_{11},y_{12},y_{13}\\}\subseteq
N_{G}(x_{4})$. Now set $X_{2}=\\{x_{5},x_{6},x_{7},x_{8}\\}$ and
$Y^{\prime\prime\prime}=\\{y_{14},y_{15},y_{16}\\}$, therefore one can check
that $|N_{G}(x)\cap Y^{\prime\prime\prime}|\geq 2$ for each $x\in
X^{\prime\prime}$. Otherwise, if there is a vertex of $X^{\prime\prime}$ say
$x^{\prime\prime}$, such that $|N_{G}(x^{\prime\prime})\cap
Y^{\prime\prime\prime}|\leq 1$, then it is easy to say that either
$|N_{G}(x^{\prime\prime})|=5$ and $|N_{G}(x^{\prime\prime})\cap Y^{\prime}\cup
Y_{3}|=3$ or $|N_{G}(x^{\prime\prime})|=4$ and $|N_{G}(x^{\prime\prime})\cap
Y^{\prime}\cup Y_{3}|=2$, in any case the Fact (F2) is true by setting
$x=x^{\prime\prime}$. Therefore as $|X_{2}|=4$, $|Y^{\prime\prime\prime}|=3$
and $|N_{G}(x)\cap Y^{\prime\prime\prime}|\geq 2$ for each $x\in
X^{\prime\prime}$, it is easy to checked that $K_{2,2}\subseteq
G[X_{2},Y^{\prime\prime\prime}]$, a contradiction.

Case 2: $|N_{G}(x_{3})|=6$. W.l.g assume that
$N_{G}(x_{3})=Y_{3}=\\{y_{2},y_{5},y_{8},y_{9},y_{10},y_{11}\\}$. Now set
$X_{2}=\\{x_{4},x_{5},x_{6},x_{7},x_{8}\\}$ and
$Y^{\prime\prime\prime}=\\{y_{12},\ldots,y_{16}\\}$. If there exists a vertex
of $X_{2}$ say $x$, such that $|N_{G}(x)\cap Y^{\prime\prime\prime}|\leq 2$,
then it is easy to say that either $|N_{G}(x)|=5$ and $|N_{G}(x)\cap
Y^{\prime}|=2$ or $|N_{G}(x)|=4$ and $|N_{G}(x)\cap Y^{\prime}|\geq 1$, in any
case the proof is complete by Case 1. Therefore, let $|N_{G}(x)\cap
Y^{\prime\prime\prime}|\geq 3$ for at lest three vertices of $x\in
X^{\prime\prime}$. Now as $|Y^{\prime\prime\prime}|=5$, its easy to say that
$K_{2,2}\subseteq G[X^{\prime\prime},Y^{\prime\prime\prime}]$, a
contradiction.

Therefore by Cases 1,2, the proof of claim is complete. ∎

Now by Claim 3.11, we have the following claim.

######  Claim 3.12.

$\Delta=5$.

###### Proof of Claim 3.12.

By contradiction, suppose that $\Delta=6$, therefore $|X^{\prime}|\geq 3$.
W.l.g let $|N_{G}(x_{1})=Y_{1}|=\Delta$ and $x_{2},x_{3},x_{4}\in X^{\prime}$.
Since $K_{2,2}\nsubseteq G$, thus $|N_{G}(x)\cap Y_{1}|\leq 1$ for each $x\in
X\setminus\\{x_{1}\\}$. Also by Claim 3.11 we have $|N_{G}(x)\cap
N_{G}(x^{\prime})|=0$ for each $x,x^{\prime}\in X^{\prime}$. So, w.l.g let
$N_{G}(x_{2})=Y_{2}=\\{y_{1},y_{2},y_{3},y_{4}\\}$,
$N_{G}(x_{3})=Y_{3}=\\{y_{5},y_{6},y_{7},y_{8}\\}$ and
$N_{G}(x_{4})=Y_{4}=\\{y_{9},y_{10},y_{11},y_{12}\\}$. Set
$W=Y\setminus(Y_{1}\cup Y_{2}\cup Y_{3})=\\{y_{13},y_{14},y_{15},y_{16}\\}$.
As $N_{G}(x_{1})=Y_{1}$ and $K_{2,2}\nsubseteq G$, we have $|Y_{1}\cap W|\geq
3$. W.l.g let $W^{\prime}=\\{y_{13},y_{14},y_{15}\\}\subseteq Y_{1}\cap W$.
Also as $|N_{G}(x)\cap W|\geq 2$ for each $x\in
X\setminus\\{x_{1},\ldots,x_{4}\\}$, then it is easy to check that
$K_{2,2}\subseteq G[\\{x_{5},x_{6},\ldots,x_{8}\\},W]$, a contradiction. Hence
claim holds. ∎

Now by Claim 3.12, and as $|E(G)|=38$, we have $|X^{\prime}|=2$. W.l.g let
$X^{\prime}=\\{x_{1},x_{2}\\}$. Also by Claim 3.11, w.l.g suppose that
$N_{G}(x_{1})=Y_{1}=\\{y_{1},y_{2},y_{3},y_{4}\\}$,
$N_{G}(x_{2})=Y_{2}=\\{y_{5},y_{6},y_{7},y_{8}\\}$. Set
$X_{1}=X\setminus\\{x_{1},x_{2}\\}$. Now we verify the next claim.

######  Claim 3.13.

For each $x\in X_{1}$ and $i=1,2$, we have $|N_{G}(x)\cap Y_{i}|=1$.

###### Proof of Claim 3.13.

By contrary, w.l.g suppose that $|N_{G}(x_{3})\cap Y_{1}|=0$. Since $|X|=8$,
and $|N_{G}(x)|=5$ for each $x\in X_{1}$, either if $|N_{G}(x_{3})\cap
Y_{2}|=0$ or there exists a vertex of $X_{1}\setminus\\{x_{3}\\}$ such that
$|N_{G}(x)\cap Y_{1}|=0$, then it is easy to say that $K_{2,2}\subseteq
G[X_{1},Y\setminus(Y_{1}\cup Y_{2})]$, a contradiction. So let
$|N_{G}(x_{3})\cap Y_{1}|=0$, $|N_{G}(x_{3})\cap Y_{2}|=1$ and w.l.g let
$N_{G}(x_{3})=Y_{3}=\\{y_{5},y_{9},y_{10},y_{11},y_{12}\\}$. Set
$X^{\prime}=X\setminus\\{x_{1}\\}$ and $Y^{\prime}=Y\setminus Y_{1}$. Since
$K_{2,2}\nsubseteq G$, we have $|N_{G}(x)\cap Y_{1}|\leq 1$ for each $x\in
X^{\prime}\setminus\\{x_{3}\\}$ and as $|N_{G}(x_{2})\cap Y_{1}|=0$ we have
$|E(G[X,Y_{1}])|\leq 9$. Therefore as $|N_{G}(x_{1})=Y_{1}|=4$, we have
$|E(G[X^{\prime},Y^{\prime}])|\geq 29$. Hence by Lemma 3.9 as
$z((7,12),K_{2,2})\leq 28$ we have $K_{2,2}\subseteq G$, a contradiction.
Hence claim holds. ∎

Therefore by Claim 3.13, we have $|N_{G}(x)\cap Y_{i}|=1$ for each $x\in
X_{1}$ and each $i=1,2$. If there is a vertex of $Y_{1}$ or $Y_{2}$ say $y$,
so that $|N_{G}(y)\cap X_{1}|\geq 3$ then as $|Y\setminus(Y_{1}\cup Y_{2})|=8$
and $|N_{G}(x)\cap Y\setminus(Y_{1}\cup Y_{2})|=3$, by pigeon-hole principle
one can check that $K_{2,2}\subseteq G$, a contradiction. Therefore we may
suppose that $|N_{G}(y)\cap X_{1}|\leq 2$ for each $x\in X_{1}$. Therefore as
$|X_{1}|=6$ and $|Y_{1}|=4$ there exist two member of $Y_{1}$ say
$y,y^{\prime}$ such that $|N_{G}(y)\cap X_{1}|=|N_{G}(y^{\prime})\cap
X_{1}|=1$. W.l.g let $y=y_{1}$ and $y^{\prime}=y_{2}$. By symmetry as
$|X_{1}|=6$ and $|Y_{2}|=4$ there exist two member of $Y_{2}$ say
$y^{\prime\prime},y^{\prime\prime\prime}$ such that
$|N_{G}(y^{\prime\prime})\cap X_{1}|=|N_{G}(y^{\prime\prime\prime})\cap
X_{1}|=1$. W.l.g let $y^{\prime\prime}=y_{5}$ and
$y^{\prime\prime\prime}=y_{6}$. Noe set
$X^{\prime}=X\setminus\\{x_{1},x_{2}\\}$ and
$Y^{\prime}=Y\setminus\\{y_{1},y_{2},y_{5},y_{6}\\}$. Since $|N_{G}(x_{i})|=4$
for each $i=1,2$, $y_{1},y_{2}\in N_{G}(x_{1})$, $y_{5},y_{6}\in N_{G}(x_{2})$
and as $|N_{G}(y)\cap X_{1}|=1$ for each $y\in Y^{\prime}$, then one can say
that $|E(G[X^{\prime},\\{y_{1},y_{2},y_{5},y_{6}\\}])|=8$ and
$|E(G[\\{x_{1},x_{2}\\},Y^{\prime}])|=4$, therefore as $|E(G)|=38$ one can
said that $|E(G[X^{\prime},Y^{\prime}]|=26$. Hence by Lemma 3.9 as
$z((6,12),K_{2,2})\leq 25$ we have $K_{2,2}\subseteq G$, a contradiction.

Hence we have the assumption that $|E(G)|=38$ and $|E(\overline{G})|=90$ does
not hold. Therefore by Lemma 2.2 as $z((8,16),K_{2,2})\leq 38$ and
$z((8,16),K_{4,4})\leq 90$, it can be said that either $K_{2,2}\subseteq G$ or
$K_{4,4}\subseteq\overline{G}$, that is $BR_{8}(K_{2,2},K_{4,4})\leq 16$.
Therefore, by Theorem 3.7, we have $BR_{8}(K_{2,2},K_{4,4})=16$, and the proof
is complete.

∎

In the following theorem, we find the value of $BR_{9}(K_{2,2},K_{3,3})$.

######  Theorem 3.14.

$BR_{9}(K_{2,2},K_{3,3})=14$.

###### Proof.

Consider $K=K_{9,14}$, let
$(X=\\{x_{1},\ldots,x_{9}\\},Y=\\{y_{1},y_{2},\ldots,y_{14}\\})$ be the
partition sets of $K$, and $G$ be a subgraph of $K$ such that
$K_{2,2}\nsubseteq G$. Consider $\Delta=\Delta(G_{X})$. By Lemma 2.5,
$\Delta\leq 6$. Now, we verify the following claim.

######  Claim 3.15.

If $\Delta=6$, then $K_{4,4}\subseteq\overline{G}$.

###### Proof of Claim 3.15.

W.l.g let $|N_{G}(x_{1})=Y_{1}|=6$. Since $K_{2,2}\nsubseteq G$, thus
$|N_{G}(x)\cap Y_{1}|\leq 1$ for each $x\in X\setminus\\{x_{1}\\}$. Therefore,
as $|X|=9$ and $|Y_{1}|=6$, if there is a vertices of $X\setminus\\{x_{1}\\}$
or a vertex of $Y_{1}$ say $x,y$ respectively, such that either $|N_{G}(x)\cap
Y_{1}|=0$ or $|N_{G}(y)\cap X\setminus\\{x_{1}\\}|\geq 3$, then by pigeon-hole
principle one can check that
$K_{4,4}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}]$. Hence, let
$|N_{G}(x)\cap Y_{1}|=1$ for each $x\in X\setminus\\{x_{1}\\}$ and
$|N_{G}(y)\cap X\setminus\\{x_{1}\\}|\leq 2$ for each $y\in Y_{1}$. Now, as
$|X|=9$ and $|Y_{1}|=6$, there exists two member of $Y_{1}$ say $y_{1},y_{2}$,
so that $|N_{G}(y_{i})\cap X\setminus\\{x_{1}\\}|=2$. W.l.g let
$N_{G}(y_{1})\cap X\setminus\\{x_{1}\\}=\\{x_{2},x_{3}\\}$ and
$N_{G}(y_{2})\cap X\setminus\\{x_{1}\\}=\\{x_{4},x_{5}\\}$. Hence,
$K_{4,4}\subseteq\overline{G}[\\{x_{2},x_{3},x_{4},x_{5}\\},Y_{1}\setminus\\{y_{1},y_{2}\\}]$,
so claim holds. ∎

Since $|E(K_{9,14})|=126$, then $38\leq|E(G)|\leq 39$ and
$87\leq|E(\overline{G})|\leq 88$. Otherwise by Lemma 2.2, as
$z((9,14),K_{2,2})\leq 39$ and $z((9,14),K_{4,4})\leq 88$, it can be said that
either $K_{2,2}\subseteq G$ or $K_{4,4}\subseteq\overline{G}$. Now we define
$A$ as follow:

$A=\\{x\in X,~{}~{}\deg_{G}(x)=5\\}.$

By Claim 3.15 and since $K_{2,2}\nsubseteq G$ and $38\leq|E(G)|\leq 39$, it is
easy to say that there exist at least two members of $X$ say $x,x^{\prime}$
such that $\Delta=\deg_{G}(x)=\deg_{G}(x^{\prime})=5$. So $|A|\geq 2$. Now we
verify the following two claims:

######  Claim 3.16.

We have $|A|\leq 3$.

###### Proof of Claim 3.16.

By contradiction, w.l.g let $|A|\geq 4$. Now consider $|E(G)|$. Since
$38\leq|E(G)|\leq 39$, if $|E(G)|=38$, then as $|X|=9$ one can said that there
exist two vertices of $X\setminus A$ say $x^{\prime},x^{\prime\prime}$ such
that for each $x\in\\{x^{\prime},x^{\prime\prime}\\}$, $|N_{G}(x_{i})|\leq 3$.
Therefore $|E(G\setminus\\{x^{\prime},x^{\prime\prime}\\})|\geq 32$. Hence by
Lemma 2.2, as $z((7,14),K_{2,2})\leq 31$ we have $K_{2,2}\subseteq
G[X\setminus\\{x_{5},x_{6}\\},Y]$, a contradiction. So suppose that
$|E(G)|=39$, then as $|X|=9$ there is one vertex of $X\setminus A$ say $x$
such that for $|N_{G}(x)|\leq 3$. Therefore we have
$|E(G\setminus\\{x\\})|\geq 36$. Hence by Lemma 2.2, as $z((8,14),K_{2,2})\leq
35$ we have $K_{2,2}\subseteq G[X\setminus\\{x\\},Y]$, a contradiction again.
Hence claim holds. ∎

######  Claim 3.17.

For each $x,x^{\prime}\in A$, $|N_{G}(x)\cap N_{G}(x^{\prime})|=1$.

###### Proof of Claim 3.17.

By contrary, w.l.g let $x_{1},x_{2}\in A$ and $|N_{G}(x_{1})\cap
N_{G}(x_{2})|=0$, $Y_{1}=N_{G}(x_{1})=\\{y_{1},\ldots,y_{5}\\}$ and
$N_{G}(x_{2})=Y_{2}=\\{y_{6},\ldots,y_{10}\\}$. By Claim 3.16 assume that
$|A|=3$ and w.l.g let $x_{3}\in A$, $N_{G}(x_{3})=Y_{3}$. As
$K_{2,2}\nsubseteq G$, one can say that $|N_{G}(x_{3})\cap
Y\setminus(Y_{1}\cup Y_{2})|\geq 3$. Therefore, since $|X|=9$, $|A|=3$, and
$|E(G)|\leq 39$, we have $|N_{G}(x)|=4$ for at least five vertices of
$X\setminus A$. Now, since $K_{2,2}\nsubseteq G$, one can say that
$|N_{G}(x)\cap Y\setminus(Y_{1}\cup Y_{2})|=2$ for this vertices. Hence, as
$|N_{G}(x_{3})\cap Y\setminus(Y_{1}\cup Y_{2})|\geq 3$, it is easy to check
that $K_{2,2}\subseteq
G[X\setminus\\{x_{1},x_{2}\\},Y\setminus(Y_{1},Y_{2})]$, a contradiction. So
let $|A|=2$. Therefore $|E(G)|=38$, and $|N_{G}(x)|=4$ for each $x\in
X\setminus A$ and $|N_{G}(x)\cap Y\setminus(Y_{1}\cup Y_{2})|\geq 2$. Hence as
$|Y\setminus(Y_{1}\cup Y_{2})|=4$ and $|X\setminus A|=7$, by pigeon-hole
principle it is easy to say that $K_{2,2}\subseteq
G[X\setminus\\{x_{1},x_{2}\\},Y\setminus(Y_{1},Y_{2})]$, a contradiction
again. So claim holds. ∎

Now, w.l.g assume that $x_{1},x_{2}\in A$ and let
$Y_{1}=\\{y_{1},\ldots,y_{5}\\}$, $Y_{2}=\\{y_{1},y_{6}\ldots,y_{9}\\}$, where
$Y_{i}=N_{G}(x_{i})$ for $i=1,2$. Define $A^{\prime}$ as follow:

$A^{\prime}=\\{x\in X\setminus A,~{}~{}\deg_{G}(x)=4\\}.$

By Claim 3.16, as $38\leq|E(G)|\leq 39$, we have $|A^{\prime}|\geq 5$. Now we
verify the next two claims:

######  Claim 3.18.

If $|A|=3$, then $y_{1}\notin N_{G}(x)$ for each $x\in
A\setminus\\{x_{1},x_{2}\\}$.

###### Proof of Claim 3.18.

W.l.g suppose that $x_{3}\in A$ and by contrary let $y_{1}\in N_{G}(x_{3})$.
Hence $|\cup_{i=1}^{i=3}Y_{i}|=13$. Assume that
$\\{y_{14}\\}=Y\setminus\cup_{i=1}^{i=3}Y_{i}$. So as $K_{2,2}\nsubseteq G$,
$y_{14}\in N_{G}(x)$ and $y_{1}\notin N_{G}(x)$ for each $x\in A^{\prime}$.
Also $|N_{G}(x)\cap Y_{i}\setminus\\{y_{1}\\}|=1$ for each $x\in A^{\prime}$
and $i=1,2$. Now, as $|Y_{1}\setminus\\{y_{1}\\}|=4$ and $|A^{\prime}|\geq 5$,
it is clear that $K_{2,2}\subseteq G[A^{\prime},\\{y,y_{14}\\}]$ for some
$y\in Y_{1}$, a contradiction. ∎

######  Claim 3.19.

If $|A|=3$, then $K_{4,4}\subseteq\overline{G}$.

###### Proof of Claim 3.19.

W.l.g let $A=\\{x_{1},x_{2},x_{3}\\}$. Also by Claim 3.18 and 3.17, w.l.g let
$N_{G}(x_{3})=Y_{3}=\\{y_{2},y_{6},y_{10},y_{11},y_{12}\\}$. Therefore
$|\cup_{i=1}^{i=3}Y_{i}|=12$. Since $|A^{\prime}|\geq 5$, w.l.g we may suppose
that $\\{x_{4},x_{5},x_{6},x_{7},x_{8}\\}\subseteq A^{\prime}$. Also one can
assume that $|N_{G}(x)\cap Y^{\prime\prime\prime}|=0$ for each $x\in
A^{\prime}$, where $Y^{\prime\prime\prime}=\\{y_{1},y_{2},y_{6}\\}$.
Otherwise, let $y_{1}\in N_{G}(x_{4})$( for other case the proof is the same).
So, as $K_{2,2}\nsubseteq G$, we have
$|N_{G}(x_{4})\cap(Y_{3}\setminus\\{y_{2},y_{6}\\})|=1$ that is
$\\{y_{13},y_{14}\\}\subseteq N_{G}(x_{4})$. Now w.l.g assume that
$N_{G}(x_{4})=\\{y_{1},y_{10},y_{13},y_{14}\\}$. Therefore it can be said that
$|N_{G}(x)\cap\\{y_{1},y_{2},y_{6},y_{10}\\}|=0$ for each $x\in
A^{\prime}\setminus\\{x_{4}\\}$, otherwise $K_{2,2}\nsubseteq
G[\\{x_{4},x\\},\\{y,y^{\prime}\\}]$ for some
$y\in\\{y_{1},y_{2},y_{6},y_{10}\\}$ and $y^{\prime}\in\\{y_{13},y_{14}\\}$, a
contradiction. Therefore,
$K_{4,4}\subseteq\overline{G}[A^{\prime}\setminus\\{x_{4}\\},\\{y_{1},y_{2},y_{6},y_{10}\\}]$.

So, let $|N_{G}(x)\cap Y^{\prime\prime\prime}|=0$ for each $x\in A^{\prime}$.
If there is a vertex of $A^{\prime}$ say $x$, such that
$|N_{G}(x)\cap\\{y_{13},y_{14}\\}|=2$, then the proof is same. Hence we may
assume that $|N_{G}(x)\cap\\{y_{13},y_{14}\\}|=1$ for each $x\in A^{\prime}$.
Also as $K_{2,2}\nsubseteq G$ for each $x\in A^{\prime}$, we have
$|N_{G}(x)\cap\\{y_{3},y_{4},y_{5}\\}|=|N_{G}(x)\cap\\{y_{7},y_{8},y_{9}\\}=|N_{G}(x)\cap\\{y_{10},y_{11},y_{12}\\}=|N_{G}(x)\cap\\{y_{13},y_{14}\\}=1$.
Therefore, as $|A^{\prime}|\geq 5$, by pigeon-hole principle there exists at
leas one member of $\\{y_{13},y_{14}\\}$ say $y_{13}$, such that
$|N_{G}(y_{13})\cap A^{\prime}|\geq 3$. As
$|N_{G}(x)\cap\\{y_{3},y_{4},y_{5}\\}|=1$, if $|N_{G}(y_{13})\cap
A^{\prime}|\geq 4$ then it is easy to check that $K_{2,2}\subseteq
G[N_{G}(y_{13})\cap A^{\prime},\\{y,y_{13}\\}]$ for some
$y\in\\{y_{3},y_{4},y_{5}\\}$, a contradiction. Hence, w.l.g let
$\\{x_{4},x_{5},x_{6}\\}=N_{G}(y_{13})\cap A^{\prime}$, that is
$x_{7},x_{8}\in N_{G}(y_{14})$.

Now, w.l.g assume that $N_{G}(x_{4})=Y_{4}=\\{y_{3},y_{7},y_{10},y_{13}\\}$,
$N_{G}(x_{5})=Y_{5}=\\{y_{4},y_{8},y_{11},y_{13}\\}$, and
$N_{G}(x_{6})=Y_{6}=\\{y_{5},y_{9},y_{12},y_{13}\\}$. Consider
$D=\\{y_{5},y_{9},y_{12}\\}$, for $i=7,8$ if there exists a vertex of $D$ say
$y$, such that $yx_{i}\in E(G)$, then $K_{2,2}\subseteq
G[\\{x_{7},x_{8}\\},\\{y,y_{14}\\}]$, a contradiction. Also there is a vertex
of $D$ say $y$, so that $yx_{7},yx_{8}\in E(\overline{G})$, otherwise
$K_{2,2}\subseteq G[\\{x_{6},x_{i}\\},D]$ for some $i\in\\{7,8\\}$, a
contradiction again. Therefore w.l.g let $x_{7}y_{5},x_{8}y_{5}\in
E(\overline{G})$, hence
$K_{4,4}\subseteq\overline{G}[\\{x_{4},x_{5},x_{7},x_{8}\\},Y^{\prime\prime\prime}\cup\\{y_{5}\\}]$.
So claim holds. ∎

Now by Claim 3.19, assume that $A=\\{x_{1},x_{2}\\}$, therefore
$A^{\prime}=X\setminus\\{x_{1},x_{2}\\}$. For $i=1,2$ set
$Y^{\prime}_{i}=Y_{i}\setminus\\{y_{1}\\}$ and set
$Y^{\prime}=\\{y_{10},\ldots,y_{14}\\}$. Now we verify two claims as follow:

######  Claim 3.20.

For each $y\in Y^{\prime}_{1}\cup Y^{\prime}_{2}$, we have $|N_{G}(y)\cap
A^{\prime}|\leq 2$.

###### Proof of Claim 3.20.

By contradiction, let $|N_{G}(y)\cap A^{\prime}|\geq 3$ for at least one $y\in
Y^{\prime}_{1}\cup Y^{\prime}_{2}$ and let $X^{\prime}=N_{G}(y)\cap
A^{\prime}$. As $|N_{G}(x)\cap Y^{\prime}|\geq 2$ and $|X^{\prime}|\geq 3$, it
can be said that $|N_{G}(y^{\prime})\cap X^{\prime}|\geq 2$ for one
$y^{\prime}\in Y^{\prime}$, which means that $K_{2,2}\nsubseteq
G[X^{\prime},\\{y,y^{\prime}\\}]$, a contradiction. ∎

By an argument similar to the proof of Claim 3.20, we can say that the
following claim is established.

######  Claim 3.21.

$|N_{G}(y_{1})\cap A^{\prime}|\leq 1$.

Now by Claim 3.21, we verify two cases as follow:

Case 1: $|N_{G}(y_{1})\cap A^{\prime}|=0$. In this case, we verify the
following claim.

######  Claim 3.22.

If there exists a vertex of $A^{\prime}$ say $x$, such that $|N_{G}(x)\cap
Y^{\prime}|=3$, then $K_{4,4}\subseteq\overline{G}$.

###### Proof of Claim 3.22.

W.l.g assume that $|N_{G}(x_{3})\cap Y^{\prime}|=3$. Therefore as
$|N_{G}(x_{3})|=4$, one can say that $|N_{G}(x_{3})\cap Y^{\prime}_{i}|=0$ for
one $i\in\\{1,2\\}$. W.l.g assume that $|N_{G}(x_{3})\cap Y^{\prime}_{1}|=0$.
Hence, as $|A^{\prime}\setminus\\{x_{3}\\}|=6$, $|Y^{\prime}_{1}|=4$, and
$|N_{G}(x)\cap Y_{1}^{\prime}|\leq 1$ for each $x\in
A^{\prime}\setminus\\{x_{3}\\}$, then one can say that there exist two
vertices of $Y^{\prime}_{1}$ say $y^{\prime}_{1},y^{\prime}_{2}$ such that
$|N_{G}(y)\cap A^{\prime}|=1$ for each
$y\in\\{y^{\prime}_{1},y^{\prime}_{2}\\}$. Also as $|A^{\prime}|=7$,
$|Y^{\prime}_{2}|=4$, and $|N_{G}(x)\cap Y_{2}^{\prime}|\leq 1$ for each $x\in
A^{\prime}\setminus\\{x_{3}\\}$, thus there exists one vertex of
$Y^{\prime}_{2}$ say $y^{\prime}_{3}$, such that $|N_{G}(y^{\prime}_{3})\cap
A^{\prime}|=1$. Set
$W=\\{y_{1},y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3}\\}$. Since
$|N_{G}(y_{1})\cap A^{\prime}|=0$, we have $|\cup_{y\in W}(N_{G}(y)\cap
A^{\prime})|\leq 3$, so since $|A^{\prime}|=7$, we have
$K_{4,4}\subseteq\overline{G}[A^{\prime},W]$. ∎

Therefore by Claim 3.22, we may suppose that $|N_{G}(x)\cap Y_{i}^{\prime}|=1$
for each $x\in A^{\prime}$ and each $i\in\\{1,2\\}$. Hence by Claim 3.20, and
using the fact that $|A^{\prime}|=7$, $|Y_{i}|=4$, it can be said that there
exists one vertex of $Y^{\prime}_{1}$ say $y^{\prime}_{1}$, and one vertex of
$Y^{\prime}_{2}$ say $y^{\prime}_{2}$, such that $|N_{G}(y)\cap A^{\prime}|=1$
for each $y\in\\{y^{\prime}_{1},y^{\prime}_{2}\\}$. Also as $|N_{G}(x)\cap
Y_{i}^{\prime}|=1$ for each $x\in X^{\prime}$ and each $i\in\\{1,2\\}$, we
have $|N_{G}(x)\cap Y^{\prime}|=2$ for each $x\in X^{\prime}$. Hence by Claim
3.20, using the fact that $|A^{\prime}|=7$ and $|Y^{\prime}|=5$, it can be
said that there exists one vertex of $Y^{\prime}$ say $y^{\prime}_{3}$, such
that $|N_{G}(y)\cap A^{\prime}|=2$. Now set
$W=\\{y_{1},y^{\prime}_{1},y^{\prime}_{2},y^{\prime}_{3}\\}$. We note that
$N_{G}(y_{1})=\\{x_{1},x_{2}\\}$. Hence assume that
$N_{G}(y^{\prime}_{1})=\\{x_{1},x^{\prime}_{1}\\}$,
$N_{G}(y^{\prime}_{2})=\\{x_{2},x^{\prime}_{2}\\}$ also let
$N_{G}(y^{\prime}_{3})=\\{x^{\prime}_{3},x^{\prime}_{4}\\}$, where
$x^{\prime}_{i}\in A^{\prime}$. If there exists $i,j\in\\{1,2,3,4\\}$, such
that $x^{\prime}_{i}=x_{j}^{\prime}$, then it can be said that $|\cup_{y\in
W}(N_{G}(y))|\leq 5$, which means that $K_{4,4}\subseteq\overline{G}[X,W]$. So
suppose that $x^{\prime}_{i}\neq x_{j}^{\prime}$ for each
$i,j\in\\{1,2,3,4\\}$. W.l.g assume that
$x_{1}^{\prime}=x_{3},x^{\prime}_{2}=x_{4},x^{\prime}_{3}=x_{5}$ and
$x^{\prime}_{4}=x_{6}$. Now consider
$X^{\prime\prime}=\\{x_{5},\ldots,x_{9}\\}$. If there exists a vertex of
$Y\setminus W$ say $y$, such that $|N_{G}(y)\cap X^{\prime\prime}|\leq 1$,
then it is easy to say that
$K_{4,4}\subseteq\overline{G}[X^{\prime\prime},\\{y_{1},y^{\prime}_{1},y^{\prime}_{2},y\\}]$.
So suppose that $|N_{G}(y)\cap X^{\prime\prime}|\geq 2$ for each $Y\setminus
W$. Therefore as $|Y\setminus W|=10$,
$N_{G}(y^{\prime}_{3})=\\{x_{5},x_{6}\\}$, and $|X^{\prime\prime}|=5$, one can
say that $|E(G[X^{\prime\prime},Y])|\geq 22$, that is there exist at least two
vertices of $X^{\prime\prime}$ with degree at least $5$, which is impossible.
Therefore, the proof of Case 1 is complete.

Case 2: $|N_{G}(y_{1})\cap A^{\prime}|=1$. W.l.g we may assume that
$N_{G}(y_{1})=\\{x_{1},x_{2},x_{3}\\}$ also let
$N_{G}(x_{3})=Y_{3}=\\{y_{1},y_{10},y_{11},y_{12}\\}$. Since $|N_{G}(x)\cap
Y_{i}^{\prime}|\leq 1$ for each $x\in A^{\prime}$ and each $i\in\\{1,2\\}$, we
have $|N_{G}(x)\cap Y^{\prime}_{4}|\geq 1$ for each $x\in
A^{\prime}\setminus\\{x_{3}\\}$, where $Y^{\prime}_{4}=\\{y_{13},y_{14}\\}$.
Set $Y^{\prime}_{i}=Y_{i}\setminus\\{y_{1}\\}$ for $i=1,2$ and
$Y^{\prime}_{3}=\\{y_{10},y_{11},y_{12}\\}$. Hence we have the following
claim.

######  Claim 3.23.

We have:

  * •

(P1): $|N_{G}(y)\cap X\setminus\\{x_{1},x_{2},x_{3}\\}|=3$ for each $y\in
Y^{\prime}_{4}=\\{y_{13},y_{14}\\}$.

  * •

(P2): $|N_{G}(x)\cap Y^{\prime}_{i}|=1$ for each $x\in
A^{\prime}\setminus\\{x_{3}\\}$ and each $i\in\\{1,2,3\\}$.

###### Proof of Claim 3.23.

Prove $(P1)$: By contradiction, w.l.g suppose that $|N_{G}(y_{13})\cap
X\setminus\\{x_{1},x_{2},x_{3}\\}|\geq 4$. W.l.g assume that
$A^{\prime\prime}=\\{x_{4},x_{5},x_{6},x_{7}\\}\subseteq N_{G}(y_{13})$. If
$|N_{G}(x)\cap\\{y_{14}\\}|=0$, then one say that $|N_{G}(x)\cap
Y^{\prime}_{3}|=1$ for each $x\in A^{\prime\prime}$, and since
$|A^{\prime\prime}|=4$ and $|Y^{\prime}_{3}|=3$, it is easy to say that
$K_{2,2}\subseteq G[A^{\prime\prime},\\{y,y_{13}\\}]$ for some $y\in
Y^{\prime}_{3}$. So suppose that $\\{y_{14}\\}\in N_{G}(x)$ for one $x\in
A^{\prime\prime}$. W.l.g assume that $y_{14}\in N_{G}(x_{4})$. If
$|N_{G}(x_{4})\cap Y^{\prime}_{3}|=1$ then the proof is same. So suppose that
$|N_{G}(x_{4})\cap Y^{\prime}_{3}|=0$, and w.l.g assume that $N_{G}(x_{4})\cap
Y^{\prime}_{1}=\\{y_{2},y_{6},y_{13},y_{14}\\}$. Now set
$B=X\setminus\\{x_{1},x_{2},x_{3},x_{4}\\}$ and
$B^{\prime}=\\{y_{1},y_{2},y_{3}\\}$. As $|N_{G}(y_{1})\cap A^{\prime}|=1$,
and for each $x\in X\setminus\\{x_{1},x_{2}\\}$, $|N_{G}(x)\cap
Y^{\prime}_{4}|\geq 1$, therefore we have
$K_{5,3}\cong[B,B^{\prime}]\subseteq\overline{G}$. Hence if there exist a
vertex of $Y\setminus B^{\prime}$ say $y$ such that $|N_{\overline{G}}(y)\cap
B|\geq 4$, then $K_{4,4}\cong[B,B^{\prime}\cup\\{y\\}]\subseteq\overline{G}$.
So let $|N_{\overline{G}}(y)\cap B|\leq 3$, that is $|N_{G}(y)\cap B|\geq 2$
for each $y\in Y\setminus B^{\prime}$. Now as $|Y\setminus B^{\prime}|=11$ one
can said that $|E(G[B,Y\setminus B^{\prime}])|\geq 22$. Therefore as $|B|=5$,
one can say that there exists at least two vertices of $B$ say $x,x^{\prime}$
such that $|N_{G}(x)|=|N_{G}(x^{\prime})|=5$, a contradiction to
$|A=\\{x_{1},x_{2}\\}|=2$.

To prove $(P2)$, if for one $x\in A^{\prime}\setminus\\{x_{3}\\}$ and one
$i\in\\{1,2,3\\}$, $|N_{G}(x)\cap Y^{\prime}_{i}|=0$, then $|N_{G}(x)\cap
Y^{\prime}_{4}|=2$. Hence as $|A^{\prime}\setminus\\{x_{3}\\}|=6$, and
$|N_{G}(x)\cap Y^{\prime}_{4}|\geq 1$ for each $x\in
A^{\prime}\setminus\\{x_{3}\\}$, then it can be cheeked that $|N_{G}(y)\cap
X\setminus\\{x_{1},x_{2},x_{3}\\}|\geq 4$ for one $y\in Y^{\prime}_{4}$, and
the proof is complete by part $(P1)$. ∎

Now by Claim 3.23, w.l.g suppose that $R=N_{G}(y_{13})\cap
X\setminus\\{x_{1},x_{2},x_{3}\\}=\\{x_{4},x_{5},x_{6}\\}$ and
$R^{\prime}=N_{G}(y_{14})\cap
X\setminus\\{x_{1},x_{2},x_{3}\\}=\\{x_{7},x_{8},x_{9}\\}$. Hence by $(P1)$
and $(P2)$ and w.l.g we can suppose the following.

  * •

(P3): $N_{G}(x_{4})=\\{y_{2},y_{6},y_{10},y_{13}\\}$.

  * •

(P4): $N_{G}(x_{5})=\\{y_{3},y_{7},y_{11},y_{13}\\}$.

  * •

(P5): $N_{G}(x_{6})=\\{y_{4},y_{8},y_{12},y_{13}\\}$.

Now consider $R^{\prime}$, by $(P2)$, w.l.g let $y_{10}\in N_{G}(x_{7})$,
$y_{11}\in N_{G}(x_{8})$, and $y_{12}\in N_{G}(x_{9})$. As $|R^{\prime}|=3$
and $|Y^{\prime}_{1}|=|Y^{\prime}_{2}|=4$ and by $(P2)$, it can be said that
the following properties are established.

  * •

(P6): There exists a vertex of $R^{\prime}$ say $x$, so that $|N_{G}(x)\cap
Y^{\prime}_{1}\setminus\\{y_{5}\\}|=|N_{G}(x)\cap
Y^{\prime}_{2}\setminus\\{y_{9}\\}|=1$.

Therefore, by $(P6)$ w.l.g we may suppose that $x=x_{7}$, $N_{G}(x_{7})\cap
Y^{\prime}_{1}\setminus\\{y_{5}\\}=\\{y^{\prime}\\}$ and $N_{G}(x_{7})\cap
Y^{\prime}_{2}\setminus\\{y_{9}\\}=\\{y^{\prime\prime}\\}$. Since $y_{10}\in
N_{G}(x_{7})$, it can be said that $y^{\prime}\neq y_{2}$ and
$y^{\prime\prime}\neq y_{6}$, otherwise either $K_{2,2}\subseteq
G[\\{x_{4},x_{7}\\},\\{y_{2},y_{10}\\}]$ or $K_{2,2}\subseteq
G[\\{x_{4},x_{7}\\},\\{y_{6},y_{10}\\}]$, a contradiction. Hence w.l.g assume
that $y^{\prime}=y_{3}$. As $y_{3},y_{7}\in N_{G}(x_{5})$, one can say that
$y^{\prime\prime}=y_{8}$. Therefore we have the following.

  * •

(P7): $N_{G}(x_{7})=\\{y_{3},y_{8},y_{10},y_{13}\\}$.

Now by considering $(P4),(P5),(P6)$, and $P(7)$ and since
$N_{G}(x_{3})\cap(Y^{\prime}_{1}\cup Y^{\prime}_{2})=\emptyset$, one can say
that
$K_{4,4}\subseteq\overline{G}[\\{x_{3},x_{5},x_{6},x_{7}\\},\\{y_{2},y_{5},y_{6},y_{9}\\}]$.
Which means that the proof of Case 2 is complete.

Therefore By Case 1 and Case 2, the proof is complete. ∎

In the following theorem, we find the values of $BR_{m}(K_{2,2},K_{3,3})$ for
each $m\in\\{10,\ldots,13\\}$.

######  Theorem 3.24.

$BR_{m}(K_{2,2},K_{4,4})=14$ for each $m\in\\{10,11,12,13\\}$.

###### Proof.

By Theorem 2.3 as $BR(K_{2,2},K_{4,4})=14$ it is sufficient to show that
$BR_{10}(K_{2,2},K_{4,4})=14$. Suppose that $G$ be a subgraph of $K_{10,14}$,
hence as $|E(K_{10,14})|=140$, then either $|E(G)|\geq 43$ or
$|E(\overline{G})|\geq 98$. Therefore by Lemma 2.2 as $z((10,14),K_{2,2})\leq
42$ and $z((10,14),K_{4,4})\leq 97$, it can be said that either
$K_{2,2}\subseteq G$ or $K_{4,4}\subseteq\overline{G}$. Therefore,
$BR_{m}(K_{2,2},K_{4,4})=14$, for each $m\in\\{10,11,12,13\\}$. ∎

###### Proof of Theorem 1.1.

For $m=2,3,4$, it is easy to say that $BR_{m}(K_{2,2},K_{3,3})$ does not
exist. Now, by combining Theorems 2.3, 3.1, 3.3, 3.7, 3.10, 3.14, and 3.24, we
conclude that the proof of Theorem 1.1 is complete. ∎

## References

  * [1] BEINERE, L., LW, B., AJ, S.: On a bipartite form of the ramsey problem. (1976)
  * [2] Bi, Z., Chartrand, G., Zhang, P.: Another view of bipartite ramsey numbers.  Discussiones Mathematicae: Graph Theory 38(2) (2018)
  * [3] Bucić, M., Letzter, S., Sudakov, B.: 3-color bipartite ramsey number of cycles and paths.  Journal of Graph Theory 92(4), 445–459 (2019)
  * [4] Bucic, M., Letzter, S., Sudakov, B.: Multicolour bipartite ramsey number of paths.  The Electronic Journal of Combinatorics pp. P3–60 (2019)
  * [5] Chartrand, G., Zhang, P.: New directions in ramsey theory.  Discrete Math. Lett 6, 84–96 (2021)
  * [6] Collins, A.F.: Bipartite Ramsey Numbers and Zarankiewicz Numbers.  Rochester Institute of Technology (2015)
  * [7] Collins, A.F., Riasanovsky, A.W., Wallace, J.C., Radziszowski, S.: Zarankiewicz numbers and bipartite ramsey numbers.  Journal of Algorithms and Computation 47, 63–78 (2016)
  * [8] Faudree, R., Schelp, R.: Path-path ramsey-type numbers for the complete bipartite graph.  Journal of Combinatorial Theory, Series B 19(2), 161–173 (1975)
  * [9] Gholami, M., Rowshan, Y.: The bipartite ramsey numbers $br(c\\_8,c\\_${$2n$}$)$.  arXiv preprint arXiv:2108.02630 (2021)
  * [10] Goddard, W., Henning, M.A., Oellermann, O.R.: Bipartite ramsey numbers and zarankiewicz numbers.  Discrete Mathematics 219(1-3), 85–95 (2000)
  * [11] Gyárfás, A., Lehel, J.: A ramsey-type problem in directed and bipartite graphs.  Period. Math. Hungar 3(3-4), 299–304 (1973)
  * [12] Hatala, I., Héger, T., Mattheus, S.: New values for the bipartite ramsey number of the four-cycle versus stars.  Discrete Mathematics 344(5), 112320 (2021)
  * [13] Hattingh, J.H., Henning, M.A.: Bipartite ramsey theory.  Utilitas Mathematica 53, 217–230 (1998)
  * [14] Hattingh, J.H., Henning, M.A.: Star-path bipartite ramsey numbers.  Discrete Mathematics 185(1-3), 255–258 (1998)
  * [15] Lakshmi, R., Sindhu, D.: Three-colour bipartite ramsey number r_b (g_1, g_2, p_3).  Electronic Journal of Graph Theory and Applications (EJGTA) 8(1), 195–204 (2020)
  * [16] Longani, V.: Some bipartite ramsey numbers.  Southeast Asian Bulletin of Mathematics 26(4), 583–592 (2003)
  * [17] Raeisi, G.: Star-path and star-stripe bipartite ramsey numbers in multicoloring.  Transactions on Combinatorics 4(3), 37–42 (2015)
  * [18] Rowshan, Y.: The multipartite ramsey numbers $m\\_j(nk\\_2,c\\_7)$.  arXiv preprint arXiv:2109.02257
  * [19] Rowshan, Y.: The multipartite ramsey numbers $m_{j}(c_{3},c_{m},n_{1}k_{2},n_{2}k_{2},\ldots,n_{i}k_{2})$.  arXiv preprint arXiv:2109.12210 (2021)
  * [20] Rowshan, Y., Gholami, M.: A proof of a conjecture on ramsey numbers $b(2,2,3)$.  arXiv preprint arXiv:2108.03572 (2021)
  * [21] Rowshan, Y., Gholami, M.: Another view of Bipartite Ramsey numbers.  arXiv e-prints arXiv:2201.12844 (2022)
  * [22] Rowshan, Y., Gholami, M., Shateyi, S.: The size, multipartite ramsey numbers for nk2 versus path–path and cycle.  Mathematics 9(7), 764 (2021)