# The $m$-bipartite Ramsey number of the $K_{2,2}$ versus $K_{6,6}$

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

Given bipartite graphs $G_{1},\ldots,G_{n}$, the bipartite Ramsey number
$BR(G_{1},\ldots,G_{n})$ is the last integer $b$ such that any complete
bipartite graph $K_{b,b}$ with edges coloured with colours $1,2,\ldots,n$
contains a copy of some $G_{i}$ ($1\leq i\leq n$) where all edges of $G_{i}$
have colour $i$. As another view of bipartite Ramsey numbers, for given
bipartite graphs $G_{1},\ldots,G_{n}$ and a positive integer $m$, the
$m$-bipartite Ramsey number $BR_{m}(G_{1},\ldots,G_{n})$, is defined as the
least integer $b$, such that any complete bipartite graph $K_{m,b}$ with edges
coloured with colours $1,2,\ldots,n$ contains a copy of some $G_{i}$ ($1\leq
i\leq n$) where all edges of $G_{i}$ have colour $i$. The size of
$BR_{m}(G_{1},G_{2})$, where $G_{1}=K_{2,2}$ and
$G_{2}\in\\{K_{3,3},K_{4,4}\\}$ for each $m$ and the size of
$BR_{m}(K_{3,3},K_{3,3})$ and $BR_{m}(K_{2,2},K_{5,5})$ for special values of
$m$, have been determined in several article up to now. In this article, we
compute the size of $BR_{m}(K_{2,2},K_{6,6})$ for some $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

Extremal graph theory problems generally ask for the max/ min order or size of
a graph having certain characteristics. Such problems 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. The Ramsey number $R(G,H)$ is the smallest order of a complete
graph, so that any $2$-coloring of the edges must result in either a copy of
graph $G$ in the first color or a copy of graph $H$ in the second color. It is
shown that $R(G,H)\leq R(K_{m},K_{n})$, where $G$ and $H$ be two arbitrary
graph of size $m$ and $n$, respectively.

Bipartite Ramsey problems deal with the same questions but the graph explored
is the complete bipartite graph instead of the complete graph. Given bipartite
graphs $G_{1},\ldots,G_{n}$, the bipartite Ramsey number
$BR(G_{1},\ldots,G_{n})$ is the last integer $b$ such that any complete
bipartite graph $K_{b,b}$ with edges coloured with colours $1,2,\ldots,n$
contains a copy of some $G_{i}$ ($1\leq i\leq n$) where all edges of $G_{i}$
have colour $i$. One can refer to [7, 9, 4, 3, 10], [15, 8, 14, 6] and their
references for further studies.

As new view of bipartite Ramsey numbers, for given bipartite graphs
$G_{1},\ldots,G_{n}$ and a positive integer $m$, the $m$-bipartite Ramsey
number $BR_{m}(G_{1},\ldots,G_{n})$, is defined as the least integer $b$, such
that any complete bipartite graph $K_{m,b}$ with edges coloured with colours
$1,2,\ldots,n$ contains a copy of some $G_{i}$ ($1\leq i\leq n$) where all
edges of $G_{i}$ have colour $i$. The size of $BR_{m}(G_{1},G_{2})$ where
$G_{1}\in\\{K_{2,2},K_{3,3}\\}$ and $G_{2}\in\\{K_{3,3},K_{4,4},K_{5,5}\\}$,
have been determined in several papers up to now. One can refer to [1, 13, 5,
2, 11, 12] and their references for further studies. In particular, The
following results have been obtained on $m$-bipartite Ramsey numbers.

######  Theorem 1.1.

[1, 13] Let $m\geq 2$, then:

$BR_{m}(K_{2,2},K_{3,3})=\left\\{\begin{array}[]{ll}\text{does not
exist},&~{}~{}~{}where~{}~{}~{}m=2,3,\vspace{.2 cm}\\\
15&~{}~{}~{}where~{}~{}~{}m=4,\vspace{.2 cm}\\\
12&~{}~{}~{}where~{}~{}~{}m=5,6,\vspace{.2 cm}\\\
9&~{}~{}~{}where~{}~{}~{}m=7,8.\vspace{.2 cm}\\\ \end{array}\right.$

######  Theorem 1.2.

[2] For each $m\in\\{1,2,\ldots,9\\}$, we have:

$BR_{m}(K_{3,3},K_{3,3})=\left\\{\begin{array}[]{ll}\text{does not
exist},&~{}~{}~{}where~{}~{}m=2,3,4,\vspace{.2 cm}\\\
41&~{}~{}~{}where~{}~{}~{}m=5,6,\vspace{.2 cm}\\\
29&~{}~{}~{}where~{}~{}~{}m=7,8.\vspace{.2 cm}\\\ \end{array}\right.$

######  Theorem 1.3.

[12] For each $m\in\\{1,2,\ldots,8\\}$, we have:

$BR_{m}(K_{2,2},K_{5,5})=\left\\{\begin{array}[]{ll}\text{does not
exist},&~{}~{}~{}where~{}~{}m=2,3,4,5,\vspace{.2 cm}\\\
40&~{}~{}~{}where~{}~{}~{}m=6,\vspace{.2 cm}\\\
30&~{}~{}~{}where~{}~{}~{}m=7,8.\vspace{.2 cm}\\\ \end{array}\right.$

In this paper, we compute the exact value of $BR_{m}(K_{2,2},K_{6,6})$ for
some $m\geq 2$ as follow.

######  Theorem 1.4.

[Main theorem] For each $m\in\\{1,2,\ldots,8\\}$, we have:

$BR_{m}(K_{2,2},K_{6,6})=\left\\{\begin{array}[]{ll}\text{does not
exist},&~{}~{}~{}where~{}~{}m=2,3,4,5,6,\vspace{.2 cm}\\\
57&~{}~{}~{}where~{}~{}~{}m=7,\vspace{.2 cm}\\\
45&~{}~{}~{}where~{}~{}~{}m=8.\vspace{.2 cm}\\\ \end{array}\right.$

Suppose that $G[X,Y]$, is a bipartite graph with bipartition sets $X$ and $Y$.
Let $E(G[X^{\prime},Y^{\prime}])$, denotes the edge set of
$G[X^{\prime},Y^{\prime}]$, where $X^{\prime}\subseteq X$ and
$Y^{\prime}\subseteq Y$. We use $\Delta(G_{X})$ and $\Delta(G_{Y})$ to denote
the maximum degree of vertices in part $X$ and $Y$ of $G$, respectively. The
degree of a vertex $v\in V(G)$, is denoted by $\deg_{G}(v)$. For each $v\in
X(Y)$, $N_{G}(v)=\\{u\in Y(X),~{}~{}vu\in E(G)\\}$. For given graphs $G$, $H$,
and $F$, we say $G$ is $2$-colorable to $(H,F)$, if there is a subgraph of $G$
say $G^{\prime}$, where $H\nsubseteq G^{\prime}$ and
$F\nsubseteq\overline{G^{\prime}}$. We use $G\rightarrow(H,F)$, to show that
$G$ is $2$-colorable to $(H,F)$. To simplify we use $[n]=\\{1,2,\ldots,n\\}$.

##  2\. Proof of the main results

In this section, we establish the main results of the paper. Before that, we
give a lemma as follow, which help to prove Theorem 1.4.

######  Lemma 2.1.

Suppose that $(X=\\{x_{1},\ldots,x_{m}\\},Y=\\{y_{1},\ldots,y_{n}\\})$, where
$m\geq 7$ and $n\geq 12$ are the partition sets of $K=K_{m,n}$. Let $G$ is a
subgraph of $K_{m,n}$. If $\Delta(G_{X})\geq 12$, then either
$K_{2,2}\subseteq G$ or $K_{6,6}\subseteq\overline{G}$.

###### Proof.

Without loss of generality (W.l.g), let $\Delta(G_{X})=12$ and
$N_{G}(x)=Y^{\prime}$, where $|Y^{\prime}|=12$ and $K_{2,2}\nsubseteq G$.
Therefore, $|N_{G}(x^{\prime})\cap Y^{\prime}|\leq 1$ for each $x^{\prime}\in
X\setminus\\{x\\}$. Since $|X|\geq 7$ and $|Y^{\prime}|=12$, so one can check
that $K_{6,6}\subseteq\overline{G}[X\setminus\\{x\\},Y^{\prime}]$. ∎

To prove Theorem 1.4, we start with the following theorem.

######  Theorem 2.2.

For each $m\in\\{2,3,4,5,6\\}$, the number $BR_{m}(K_{2,2},K_{6,6})$ does not
exist.

###### Proof.

Suppose that $m\in\\{2,3,4,5,6\\}$. For an arbitrary integer $t\geq 6$, set
$K=K_{m,t}$ and let $G$ be a subgraph of $K$, such that $G=K_{1,t}$.
Therefore, we have $\overline{G}=K_{m-1,t}$. Hence, one can checked that,
neither a $K_{2,2}\subseteq G$ nor a $K_{6,6}\subseteq\overline{G}$. Therefore
for each $m\in\\{2,3,4,5,6\\}$, the number $BR_{m}(K_{2,2},K_{6,6})$ does not
exist. ∎

In the next results, we determined the size of $BR_{m}(K_{2,2},K_{6,6})$ for
$m=7$.

######  Theorem 2.3.

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

###### Proof.

Suppose that $(X=\\{x_{1},\ldots,x_{7}\\},Y=\\{y_{1},y_{2},\ldots,y_{56}\\})$
are the partition sets of $K=K_{7,56}$. Let $G\subseteq K$, such that
$N_{G}(x_{i})=Y_{i}$, with the following properties:

  * •

(A1): $Y_{1}=\\{y_{1},y_{2},\ldots,y_{11}\\}$.

  * •

(A2): $Y_{2}=\\{y_{1},y_{12},y_{11}\ldots,y_{21}\\}$.

  * •

(A3): $Y_{3}=\\{y_{2},y_{12},y_{22},y_{23}\ldots,y_{30}\\}$.

  * •

(A4): $Y_{4}=\\{y_{3},y_{13},y_{22},y_{31},\ldots,y_{38}\\}$.

  * •

(A5): $Y_{5}=\\{y_{4},y_{14},y_{23},y_{31},y_{39},y_{40},\ldots,y_{45}\\}$.

  * •

(A6):
$Y_{6}=\\{y_{5},y_{15},y_{24},y_{32},y_{39},y_{46},y_{47},\ldots,y_{51}\\}$.

  * •

(A7):
$Y_{7}=\\{y_{6},y_{16},y_{25},y_{33},y_{40},y_{46},y_{52},\ldots,y_{56}\\}$.

So, for each $i,j\in[6]$, by $(Ai)$ and $(Aj)$, one can checked that
$|N_{G}(x_{i})\cap N_{G}(x_{j})|=1$, and $|\cup_{j=1,j\neq
i}^{j=7}N_{G}(x_{j})|=51$. Therefore, $K_{2,2}\nsubseteq G$ and
$K_{6,6}\nsubseteq\overline{G}[X\setminus\\{x_{i}\\},Y]$ for each $i\in[7]$.
Hence, $BR_{7}(K_{2,2},K_{6,6})\geq 57$.

Now, suppose that $(X=\\{x_{1},\ldots,x_{7}\\},Y=\\{y_{1},\ldots,y_{57}\\})$
are the partition sets of $K=K_{7,57}$. Suppose that $G$ be a subgraph of $K$,
so that $K_{2,2}\nsubseteq G$. Consider $\Delta=\Delta(G_{X})$. One can
suppose that $\Delta\in\\{9,10,11\\}$. Otherwise, if $\Delta\geq 12$, then
theorem holds by Lemma 2.1. Also for the case that $\Delta\leq 8$, it is clear
that $K_{6,6}\subseteq\overline{G}$. Now, we the following claims.

######  Claim 2.4.

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

###### Proof of Claim 2.4.

W.l.g let $N_{G}(x_{1})=Y_{1}=\\{y_{1},\ldots,y_{9}\\}$. As $K_{2,2}\nsubseteq
G$, we have $|N_{G}(x_{i})\cap N_{G}(x_{j})|\leq 1$ for each $i,j\in[7]$.
Also, it can be checked that $|N_{G}(x)\cap Y_{1}|=1$ for at least four
members of $X\setminus\\{x_{1}\\}$, otherwise
$K_{6,6}\subseteq\overline{G}[X,Y_{1}]$. W.l.g let $|N_{G}(x)\cap Y_{1}|=1$
for each $x_{i}\in\\{x_{2},x_{3},x_{4},x_{5}\\}$. Therefore, as $\Delta=9$ and
$|N_{G}(x)\cap Y_{1}|=1$ for each $x_{i}\in\\{x_{2},x_{3},x_{4},x_{5}\\}$,
then one can check that $|\cup_{j=1}^{j=5}N_{G}(x_{j})|\leq 41$. Hence, as
$N_{G}(x_{6})\leq\Delta=9$, then we have $|\cup_{j=1}^{j=6}N_{G}(x_{j})|\leq
50$. Therefore as $|Y|=57$, we have
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{7}\\},Y]$, hence the claim
holds. ∎

######  Claim 2.5.

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

###### Proof of Claim 2.5.

W.l.g let $N_{G}(x_{1})=Y_{1}=\\{y_{1},\ldots,y_{10}\\}$. As
$K_{2,2}\nsubseteq G$, we have $|N_{G}(x_{i})\cap N_{G}(x_{j})|\leq 1$ for
each $i,j\in[7]$. Also, it can be checked that $|N_{G}(x)\cap Y_{1}|=1$ for at
least five members of $X\setminus\\{x_{1}\\}$, otherwise
$K_{6,6}\subseteq\overline{G}[X,Y_{1}]$. W.l.g let $|N_{G}(x)\cap Y_{1}|=1$
for each $x\in X^{\prime}=\\{x_{2},x_{3},x_{4},x_{5},x_{6}\\}$. Therefore, as
$\Delta=10$ and $|N_{G}(x)\cap Y_{1}|=1$ for each $x\in X^{\prime}$, then one
can check that $|\cup_{j=1}^{j=5}N_{G}(x_{j})|\leq 55$. If
$|N_{G}(x)\cap(Y\setminus Y_{1})|\leq 8$ for at least four members of
$X^{\prime}$, then one can check that $|\cup_{j=1}^{j=6}N_{G}(x_{j})|\leq 51$.
Therefore, as $|Y|=57$, we have
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{7}\\},Y]$, that is the claim is
true. Now, suppose that $|N_{G}(x)\cap(Y\setminus Y_{1})|=9$ for at least two
members of $X^{\prime}$. W.l.g let $|N_{G}(x)\cap(Y\setminus Y_{1})|=9$ for
each $x\in\\{x_{2},x_{3}\\}$. For $i=2,3$, we may suppose that
$N_{G}(x_{i})\cap(Y\setminus Y_{1})=Y_{i}$. As $|Y_{i}|=9$, if $|Y_{2}\cap
Y_{3}|=0$, then it is easy to check that $|N_{G}(x)\cap Y_{i}|=1$ for each
$x\in\\{x_{4},x_{5},x_{6}\\}$. Otherwise, one can say that
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{i}\\},Y_{i}]$ for some
$i\in\\{2,3\\}$. So, we have $|\cup_{j=1}^{j=6}N_{G}(x_{j})|\leq
10+9+9+7+7+7=49$, hence the proof is the same. So, let $|Y_{2}\cap Y_{3}|=1$.
Therefore, we have $|\cup_{j=1}^{j=3}N_{G}(x_{j})|=27$. If $|N_{G}(x)\cap
Y_{i}|=1$ for each $x\in\\{x_{4},x_{5},x_{6}\\}$, then the proof is the same.
Now, for each $j=4,5,6$, let $|N_{G}(x_{j})\cap Y_{i}|=1$ for at least one
$i\in\\{2,3\\}$. Therefore, we have $|N_{G}(x)\cap(Y_{1}\cup Y_{2}\cup
Y_{3})|\geq 2$, that is $|N_{G}(x)\cap(Y\setminus Y_{1}\cup Y_{2}\cup
Y_{3})|\leq 8$ for each $x\in\\{x_{4},x_{5},x_{6}\\}$. So, we have
$|\cup_{j=1}^{j=6}N_{G}(x_{j})|\leq 10+9+8+8+8+8=51$. Therefore, we have
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{7}\\},Y]$. Now, let there is a
member of $\\{x_{4},x_{5},x_{6}\\}$ say $x$, such that $|N_{G}(x)\cap
Y_{i}|=0$ for each $i=2,3$, w.l.g let $x=x_{4}$. As $|Y_{3}|=9$, $|Y_{2}\cap
Y_{3}|=1$, and $|N_{G}(x_{4})\cap Y_{i}|=0$, it is easy to check that
$|N_{G}(x)\cap Y_{i}|=1$ for each $x\in\\{x_{5},x_{6}\\}$ and each
$i\in\\{2,3\\}$. Otherwise, one can say that
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{i}\\},Y_{i}]$ for some $i=2,3$.
So, we have $|\cup_{j=1,j\neq 4}^{j=6}N_{G}(x_{j})|\leq 10+9+8+7+7=41$.
Therefore, as $\Delta=10$, $|N_{G}(x_{4})\cap Y_{1}|=1$, we have
$|\cup_{j=1}^{j=6}N_{G}(x_{j})|\leq 50$, that is
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{7}\\},Y]$. Hence claim holds. ∎

Therefore, by Claims 2.4, 2.5, let $\Delta=11$. W.l.g let $|N_{G}(x_{1})|=11$
and $Y_{1}=N_{G}(x_{1})=\\{y_{1},\ldots,y_{11}\\}$. Now, we have the following
claim.

######  Claim 2.6.

If either $|N_{G}(x_{i})\cap Y_{1}|=0$ or $N_{G}(x_{i})\cap
Y_{1}=N_{G}(x_{j})\cap Y_{1}$ for some $i,j\in\\{2,\ldots,7\\}$, then
$K_{6,6}\subseteq\overline{G}$.

###### Proof of Claim 2.6.

As $K_{2,2}\nsubseteq G$, so $|N_{G}(x_{i})\cap Y_{1}|\leq 1$ for each $i$.
Now, let $|N_{G}(x_{2})\cap Y_{1}|=0$. Therefore, it is clear that
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}]$. Also, w.l.g let
$N_{G}(x_{2})\cap N_{G}(x_{3})\cap Y_{1}=\\{y\\}$, then as $|X|=7$ and
$|Y_{1}|=11$, we have
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}\setminus\\{y\\}]$. ∎

Therefore, by Claim 2.6 it is clear that
$K_{6,5}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}]$. If
$|N_{G}(x)|=11$ for each $x\in X$, then by Claim 2.6 we have
$|\cup_{j=1}^{j=6}N_{G}(x_{j})|=56$, that is there exists a member of $Y$ say
$y_{57}$, such that $|N_{G}(y_{57})|=0$. Therefore, we have
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}\cup\\{y_{57}\\}]$
and the proof is complete.

So, assume that $|N_{G}(x)|\leq 10$ for at least one member of
$X\setminus\\{x_{1}\\}$. W.l.g let $\deg_{G}(x_{2})=10$ and
$N_{G}(x_{2})=Y_{2}=\\{y_{1},y_{12},y_{13}\ldots,y_{20}\\}$. One can suppose
that there is at least four members of $X\setminus\\{x_{1},x_{2}\\}$, say
$X^{\prime}=\\{x_{3},x_{4},x_{5},x_{6}\\}$, so that for each
$i,j\in\\{3,4,5,6\\}$, $|N_{G}(x_{i})\cap Y_{2}\setminus\\{y_{1}\\}|=1$ and
$N_{G}(x_{i})\cap Y_{2}\setminus\\{y_{1}\\}\neq N_{G}(x_{j})\cap
Y_{2}\setminus\\{y_{1}\\}$. Otherwise, by an argument similar to the proof of
Claim 2.6, we have
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{2}\\},Y_{2}]$. Therefore, as
$\Delta=11$, and $|N_{G}(x_{i})\cap Y_{i}\setminus\\{y_{1}\\}|=1$ for each
$x\in X^{\prime}$ and each $i=1,2$, one can check that
$|\cup_{j=1}^{j=6}N_{G}(x_{j})|\leq 11+9+9+9+9+9=56$. Hence, the proof is the
same as the case that $|N_{G}(x)|=11$ for each $x\in X$. So, the theorem
holds. ∎

In the next results, we determined the size of $BR_{8}(K_{2,2},K_{6,6})$.

######  Theorem 2.7.

$BR_{8}(K_{2,2},K_{6,6})=45$.

###### Proof.

Let $(X=\\{x_{1},\ldots,x_{8}\\},Y=\\{y_{1},\ldots,y_{44}\\})$ are the
partition sets of $K=K_{8,44}$. Suppose that $G$ be a subgraph of $K$ such
that for each $i\in[8]$, $N_{G}(x_{i})=Y_{i}$ with the following properties.

  * •

(B1): $Y_{1}=\\{y_{1},\ldots,y_{9}\\}$.

  * •

(B2): $Y_{2}=\\{y_{1},y_{10},y_{11},\ldots,y_{17}\\}$.

  * •

(B3): $Y_{3}=\\{y_{2},y_{10},y_{18},y_{19},\ldots,y_{24}\\}$.

  * •

(B4):
$Y_{4}=\\{y_{3},y_{11},y_{18},y_{25},y_{26},y_{27},y_{28},y_{29},y_{30}\\}$.

  * •

(B5):
$Y_{5}=\\{y_{4},y_{12},y_{19},y_{25},y_{31},y_{32},y_{33},y_{34},y_{35}\\}$.

  * •

(B6):
$Y_{6}=\\{y_{5},y_{13},y_{20},y_{26},y_{31},y_{36},y_{37},y_{38},y_{39}\\}$.

  * •

(B7):
$Y_{7}=\\{y_{6},y_{14},y_{21},y_{27},y_{32},y_{36},y_{40},y_{41},y_{42}\\}$.

  * •

(B8):
$Y_{8}=\\{y_{7},y_{15},y_{22},y_{28},y_{33},y_{37},y_{40},y_{43},y_{44}\\}$.

By considering $(Bi)$ and $(Bj)$, it can be said that:

  * •

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

  * •

(C2): $|\cup_{i=1}^{i=6}N_{G}(x_{j_{i}})|=39$, for each
$j_{1},\ldots,j_{6}\in[8]$.

Therefore by $(C1)$, we have $K_{2,2}\nsubseteq G$. Also, by $(C2)$, one can
check that $K_{6,6}\nsubseteq\overline{G}$, which means that
$K_{8,44}\rightarrow(K_{2,2},K_{6,6})$. Therefore, the lower bound holds.

Now, we prove the upper bound. We may suppose that
$(X=\\{x_{1},\ldots,x_{8}\\},Y=\\{y_{1},\ldots,y_{45}\\})$ are the partition
sets of $K=K_{8,45}$. Let $G$ be a subgraph of $K$, where $K_{2,2}\nsubseteq
G$. We show that $K_{6,6}\subseteq\overline{G}$. Consider
$\Delta=\Delta(G_{X})$. As $K_{2,2}\nsubseteq G$, then by Lemma 2.1, one can
assume that $\Delta\leq 11$. Hence:

######  Claim 2.8.

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

###### Proof of Claim 2.8.

W.l.g let $|N_{G}(x_{1})=Y_{1}|=11$. Since $K_{2,2}\nsubseteq G$, $|X|=8$, and
$|Y_{1}|=11$, then one can suppose that $|N_{G}(x_{i})\cap Y_{1}|=1$, and for
each $i,j\in\\{2,\ldots,8\\}$, $x_{i}$ and $x_{j}$ have a different
neighborhood in $Y_{1}$. Otherwise, in any case it is clear that
$K_{6,6}\subseteq\overline{G}[X,Y_{1}]$. Therefore, for each $x\neq x_{1}$, we
have $K_{6,5}\subseteq\overline{G}[X\setminus\\{x_{1},x\\},Y_{1}]$. If there
is a member of $Y\setminus Y_{1}$ say $y$, such that
$|N_{\overline{G}}(y)\cap(X\setminus\\{x_{1}\\})|\geq 6$, then
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}\cup\\{y\\}]$. Hence,
let $|N_{G}(y)\cap(X\setminus\\{x_{1}\\})|\geq 2$ for each $y\in Y\setminus
Y_{1}$. Therefore, $|E(G[X\setminus\\{x_{1}\\},Y\setminus Y_{1}])|\geq
34\times 2=68$. Hence, by pigeon-hole principle, there is at least one member
of $X\setminus\\{x_{1}\\}$ say $x_{2}$, such that
$|N_{G}(x_{2})\cap(Y\setminus Y_{1})|\geq 10$. Set
$N_{G}(x_{2})\cap(Y\setminus Y_{1})=Y_{2}$. Now, as $K_{2,2}\nsubseteq G$,
then $|N_{G}(x_{i})\cap Y_{2}|\leq 1$ for each $i\in\\{3,\ldots,8\\}$.
Therefore, since $|Y_{2}|\geq 10$, one can checked that
$K_{6,1}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{2}]$. Hence, as
$K_{6,5}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}]$, we have
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}\cup Y_{2}]$.
So, the claim holds. ∎

Therefore, by Claim 2.8, one can assume that $\Delta\leq 10$. Now, we have the
next claim.

######  Claim 2.9.

If there exist $V\subseteq X$, such that $|V|=5$ and $|\cup_{x\in
V}N_{G}(x)|\leq 35$, then we have $K_{6,6}\subseteq\overline{G}$.

###### Proof of Claim 2.9.

W.l.g assume that $V=\\{x_{1},x_{2},x_{3},x_{4},x_{5}\\}$ and let
$Y^{\prime}=\cup_{x\in V}N_{G}(x)$ where $|Y^{\prime}|\leq 35$. If
$|Y^{\prime}|\leq 29$, then as $\Delta\leq 10$, it is easy to said that
$|Y^{\prime}\cup N_{G}(x)|\leq 39$ for each $x\in X\setminus V$, that is
$K_{6,6}\subseteq\overline{G}[V\cup\\{x\\},Y]$, hence the claim holds. So,
suppose that $|Y^{\prime}|\in\\{30,\ldots,34,35\\}$. Assume that
$|Y^{\prime}|=35$. Hence, for each $x\in\\{x_{6},x_{7},x_{8}\\}$, one can
assume that $|N_{G}(x)\cap Y\setminus Y^{\prime}|\geq 5$, otherwise we have
$|Y^{\prime}\cup N_{G}(x)|\leq 39$ for some $x\in X\setminus V$, that is
$K_{6,6}\subseteq\overline{G}$. Therefore, as
$|Y\setminus\cup_{i=1}^{i=5}N_{G}(x_{i})|=10$ and
$|\\{x_{6},x_{7},x_{8}\\}|=3$, it easy to say that $K_{2,2}\subseteq
G[\\{x_{6},x_{7},x_{8}\\},Y\setminus\cup_{i=1}^{i=5}N_{G}(x_{i})]$, a
contradiction. Now let $|Y^{\prime}|=34$. Hence, for each
$x\in\\{x_{6},x_{7},x_{8}\\}$, one can assume that $|N_{G}(x)\cap Y\setminus
Y^{\prime}|\geq 6$, otherwise $|Y^{\prime}\cup N_{G}(x)|\leq 39$ for some
$x\in X\setminus V$, that is we have $K_{6,6}\subseteq\overline{G}$.
Therefore, as $|Y\setminus\cup_{i=1}^{i=5}N_{G}(x_{i})|=11$ and
$|\\{x_{6},x_{7},x_{8}\\}|=3$, it easy to say that $K_{2,2}\subseteq
G[\\{x_{6},x_{7},x_{8}\\},Y\setminus\cup_{i=1}^{i=5}N_{G}(x_{i})]$, a
contradiction again. For the case that $|Y^{\prime}|\in\\{30,31,32,33\\}$, the
proof is the same. Hence, the claim holds. ∎

If $\Delta\leq 6$, then it is clear that $K_{6,6}\subseteq\overline{G}$. Now,
we may suppose that $\Delta=7$, and w.l.g let $|N_{G}(x_{1})=Y_{1}|=7$. One
can assume that $|N_{G}(x)\cap Y_{1}|=1$ for at least three members of
$X\setminus\\{x_{1}\\}$. Otherwise, as $|Y_{1}|=|X\setminus\\{x_{1}\\}|=7$ and
$|N_{G}(x)\cap Y_{1}|\leq 1$ for each member of $X\setminus\\{x_{1}\\}$. Then
it is easy to say that $K_{6,6}\subseteq\overline{G}[X,Y_{1}]$. Hence, w.l.g
assume that $|N_{G}(x)\cap Y_{1}|=1$ for each members of
$\\{x_{2},x_{3},x_{4}\\}$. Hence as $\Delta=7$, one can check that
$|\cup_{i=1}^{i=4}N_{G}(x_{i})|=25$. Therefore, we have
$|\cup_{i=1}^{i=5}N_{G}(x_{i})|\leq 32$, and by Claim 2.9, we have
$K_{6,6}\subseteq\overline{G}$. So, we may suppose that
$\Delta\in\\{8,9,10\\}$. Now we consider the following cases.

Case 1. $\Delta=8$. W.l.g suppose that $\Delta=|N_{G}(x_{1})=Y_{1}|$. As
$K_{2,2}\nsubseteq G$, one can suppose that there exists at least four members
of $X\setminus\\{x_{1}\\}$ say $X^{\prime}=\\{x_{2},\ldots,x_{5}\\}$, such
that $|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,\ldots,5\\}$. Otherwise, one can
check that $K_{7,5}\subseteq\overline{G}[X\setminus\\{x_{1}\\},Y_{1}]$.
Therefore, for each $y\in Y\setminus Y_{1}$, one can suppose that
$|N_{G}(y)\cap X\setminus\\{x_{1}\\}|\geq 2$, Otherwise
$K_{6,6}\subseteq\overline{G}$. So, as $|Y\setminus Y_{1}|=37$, we have
$|E(G[X\setminus\\{x_{1}\\},Y\setminus Y_{1}])|\geq 74$. Therefore, by pigeon-
hole principle there is at least one member of $X\setminus\\{x_{1}\\}$ say
$x$, such that $|N_{G}(x)|\geq 10$, a contradiction. Now, w.l.g suppose that
$Y_{1}=\\{y_{1},\ldots,y_{8}\\}$ and $x_{i}y_{i-1}\in E(G)$ for each
$i=2,3,4,5$. Set $Y^{\prime}=\cup_{i=1}^{i=5}N_{G}(x_{i})$. Hence, it is easy
to say that $|Y^{\prime}|\leq 36$. If $|Y^{\prime}|\leq 35$, then proof is
complete by Claim 2.9. So, let $|Y^{\prime}|=36$. That is
$\Delta=8=|N_{G}(x_{i})|$ for each $i\in[5]$ and $|N_{G}(x_{i})\cap
N_{G}(x_{j})|=0$ for each $i,j\in\\{2,3,4,5\\}$. Now consider $i=2,3$, as
$K_{2,2}\nsubseteq G$, we have
$|N_{G}(x_{j})\cap(N_{G}(x_{i})\setminus\\{y_{i-1}\\})|\leq 1$ for each
$j\in\\{6,7\\}$, hence one can say that
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{2},x_{3}\\},N_{G}(x_{2})\cup
N_{G}(x_{2})\setminus\\{y_{1},y_{2}\\}]$.

Case 2. $\Delta=9$. W.l.g suppose that
$N_{G}(x_{1})=Y_{1}=\\{y_{1},y_{2},\ldots,y_{9}\\}$. Now, set $A$ as follow:

$A=\\{x\in X,~{}~{}|N_{G}(x)|=\Delta=9\\}$

As $K_{2,2}\nsubseteq G$, we have $|N_{G}(x_{i})\cap Y_{1}|\leq 1$. Hence, one
can say that $K_{6,3}\subseteq\overline{G}[X\setminus\\{x_{1},x\\},Y_{1}]$ for
each $x\in\\{x_{2},\ldots,x_{8}\\}$. Therefore, by considering the members of
$A$, one can check that the following claim is true.

######  Claim 2.10.

If $|N_{G}(x)\cap N_{G}(x^{\prime})|=0$ for some $x,x^{\prime}\in A$, then
$K_{6,6}\subseteq\overline{G}$.

Therefore, by Claims 2.10, we can prove the following claim.

######  Claim 2.11.

If $|N_{G}(x)\cap N_{G}(x^{\prime})\cap N_{G}(x^{\prime\prime})|=1$ for some
$x,x^{\prime},x^{\prime\prime}\in A$, then $K_{6,6}\subseteq\overline{G}$.

###### Proof of Claim 2.11.

W.l.g assume that $x_{1},x_{2},x_{3}\in A$, $\\{y_{1}\\}=Y_{1}\cap Y_{2}\cap
Y_{3}$, where $Y_{i}=N_{G}(x_{i})$ for $i=1,2,3$. Since $K_{2,2}\nsubseteq G$,
for each $i\in[3]$ and each $x\in X\setminus\\{x_{1},x_{2},x_{3}\\}$ we have
$|N_{G}(x)\cap Y_{i}|\leq 1$. Therefore, as $|Y_{i}|=9$, and $|N_{G}(x)\cap
Y_{i}|\leq 1$ for each $x\in X\setminus\\{x_{1},x_{2},x_{3}\\}$, it is easy to
say that
$K_{5,3}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2},x_{3}\\},Y_{i}\setminus\\{y_{1}\\}]$
for each $i\in[3]$. Therefore, we have
$K_{5,6}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2},x_{3}\\},Y_{1}\cup
Y_{2}\setminus\\{y_{1}\\}]$. So, as $y_{1}\in Y_{1}\cap Y_{2}\cap Y_{3}$ and
$K_{2,2}\nsubseteq G$, then $N_{G}(x_{3})\cap(Y_{1}\cup
Y_{2}\setminus\\{y_{1}\\})=\emptyset$. Therefore,
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}\cup
Y_{2}\setminus\\{y_{1}\\}]$. Hence, the claim holds. ∎

Consider $|A|$. First suppose that $|A|\geq 5$, and w.l.g assume that
$\\{x_{1},x_{2},x_{3},x_{4},x_{5}\\}\subseteq A$. Therefore, by Claim 2.10 and
2.11, it can be said that $|\cup_{i=1}^{i=5}N_{G}(x_{i})|=35$. Hence, by Claim
2.9 the proof is complete. So, we may assume that $|A|\leq 4$. Now, we verify
the following two claims.

######  Claim 2.12.

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

###### Proof of Claim 2.12.

W.l.g assume that $A=\\{x_{1},x_{2},x_{3},x_{4}\\}$. Therefore, by Claims 2.10
and 2.11, one can checked that $|\cup_{i=1}^{i=4}N_{G}(x_{i})|=30$. Set
$Y^{\prime}=\cup_{i=1}^{i=4}N_{G}(x_{i})$. If there is a member of $X\setminus
A$ say $x$, so that $3\leq|N_{G}(x)\cap Y^{\prime}|$, then
$|\cup_{i=1}^{i=5}N_{G}(x_{i})\cup N_{G}(x)|\leq 35$ and the proof is complete
by Claim 2.9.

Hence, we may suppose that $|N_{G}(x)\cap Y^{\prime}|\leq 2$ for each $x\in
X\setminus A$. So as $|Y^{\prime}|=30$, one can checked that
$K_{4,22}\subseteq\overline{G}[X\setminus A,Y^{\prime}]$. W.l.g let
$K_{4,22}\cong\overline{G}[X\setminus A,Y^{\prime\prime}]$, where
$Y^{\prime\prime}\subseteq Y^{\prime}$ and $|Y^{\prime\prime}|=22$. Therefore,
it is easy to checked that there is at least two members of $A$ say
$x_{i_{1}}x_{i_{2}}$, such that $|(N_{G}(x_{i_{1}})\cup N_{G}(x_{i_{1}}))\cap
Y^{\prime\prime}|\leq 16$. W.l.g let $i_{1}=1,i_{2}=2$. So, we have
$K_{6,6}\cong\overline{G}[X\setminus\\{x_{3},x_{4}\\},Y^{\prime\prime}]$.
Hence, the claim holds. ∎

######  Claim 2.13.

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

###### Proof of Claim 2.13.

W.l.g suppose that $A=\\{x_{1},x_{2},x_{3}\\}$. Therefore, by Claims 2.10 and
2.11, it can be said that $|\cup_{i=1}^{i=3}N_{G}(x_{i})|=24$. Set
$Y^{\prime}=\cup_{i=1}^{i=3}N_{G}(x_{i})$. Suppose that there exists a vertex
of $X\setminus A$ say $x$, such that $|N_{G}(x)\cap Y^{\prime}|\geq 2$, then
we have $|\cup_{i=1}^{i=4}N_{G}(x_{i})\cup N_{G}(x)|\leq 30$. W.l.g assume
that $x=x_{4}$. If $|\cup_{i=1}^{i=4}N_{G}(x_{i})|\leq 27$, then the proof is
complete by Claim 2.9. So, suppose that
$28\leq|\cup_{i=1}^{i=4}N_{G}(x_{i})|\leq 30$. Let
$|\cup_{i=1}^{i=4}N_{G}(x_{i})|=30$. Set
$X^{\prime}=\\{x_{5},x_{6},x_{7},x_{8}\\}$. In this case, one can suppose that
$|N_{G}(x)\cap(Y\setminus\cup_{i=1}^{i=4}N_{G}(x_{i}))|\geq 6$ for each $x\in
X^{\prime}$. Otherwise, the proof is complete by Claim 2.9. Therefore, as
$|X^{\prime}|=4$ and $|Y\setminus\cup_{i=1}^{i=4}N_{G}(x_{i}))|=15$, then one
can checked that $K_{2,2}\subseteq G$, a contradiction. For the case that
$|\cup_{i=1}^{i=4}N_{G}(x_{i})|=28,29$, the proof is the same.

So, let $|N_{G}(x)\cap Y^{\prime}|\leq 1$ for each $x\in X\setminus A$.
Therefore, it is clear that $K_{5,19}\subseteq\overline{G}[X\setminus
A,Y^{\prime}]$. W.l.g let $K_{5,19}\cong\overline{G}[X\setminus
A,Y^{\prime\prime}]$, where $Y^{\prime\prime}\subseteq Y^{\prime}$ and
$|Y^{\prime\prime}|=19$. Therefore, one can said that there is at least one
member of $A$ say $y$, so that $|N_{G}(y)\cap Y^{\prime\prime}|\leq 9$. W.l.g
let $y=y_{1}$. So
$K_{6,6}\cong\overline{G}[X\setminus\\{x_{2},x_{3}\\},Y^{\prime\prime}]$.
Hence, the claim holds. ∎

Hence, by Claims 2.12 and 2.13, one can suppose that $|A|\leq 2$. First,
assume that $|A|=2$ and w.l.g suppose that $A=\\{x_{1},x_{2}\\}$. By Claim
2.11, we have $|\cup_{i=1}^{i=2}N_{G}(x_{i})|=17$. For $i=1,2$, set
$Y_{i}=N_{G}(x_{i})$. By Claim 2.11 w.l.g let $y_{1}\in Y_{1}\cap Y_{2}$. Set
$X^{\prime}=X\setminus A$. Suppose that there is at least two vertices of
$X^{\prime}$ say $x_{3},x_{4}$, such that $|N_{G}(x)\cap
Y_{i}\setminus\\{y_{1}\\}|=0$ for at least one $i\in[2]$. W.l.g let
$|N_{G}(x)\cap Y_{1}\setminus\\{y_{1}\\}|=0$, therefore as $|N_{G}(x)\cap
Y_{1}\setminus\\{y_{1}\\}|\leq 1$ and $|Y_{1}|=9$, one can say that
$K_{6,4}\subseteq\overline{G}[X\setminus A,Y_{1}\setminus\\{y_{1}\\}]$. Also,
one can check that $K_{6,2}\subseteq\overline{G}[X\setminus
A,Y_{2}\setminus\\{y_{1}\\}]$, hence $K_{6,6}\subseteq\overline{G}[X\setminus
A,Y_{1}\cup Y_{2}\setminus\\{y_{1}\\}]$. Therefore for any $i\in\\{1,2\\}$, we
may suppose that $|N_{G}(x)\cap Y_{i}\setminus\\{y_{1}\\}|=1$ for at least
five members of $X^{\prime}$. Hence as $|X^{\prime}|=6$, it is clear that
there is at least three member of $X^{\prime}$ say $\\{x_{3},x_{4},x_{5}\\}$,
so that for any $x\in\\{x_{3},x_{4},x_{5}\\}$, we have
$|N_{G}(x)\cap(Y_{1}\cup Y_{2}\setminus\\{y_{1}\\})|=2$. Therefore, as
$|N_{G}(x)|\leq 8$ for each $i=3,4,5$, one can check that
$|\cup_{i=1}^{i=5}N_{G}(x_{i})|\leq 17+18=35$. Hence, the proof is complete by
Claim 2.9.

Now, let $|A|=1$ and w.l.g let $A=\\{x_{1}\\}$. In this case, one can say that
there exist at least five vertices of $X\setminus\\{x_{1}\\}$ say
$X^{\prime\prime}=\\{x_{2},x_{3},x_{4},x_{5},x_{6}\\}$, such that
$|N_{G}(x)\cap Y_{1}|=1$ for each $x\in X^{\prime\prime}$. Otherwise, as
$|Y_{1}|=9$ and $|N_{G}(x)\cap Y_{1}|\leq 1$ for each $x\in
X\setminus\\{x_{1}\\}$, then one can say that
$K_{6,6}\cong\overline{G}[X\setminus\\{x_{1}\\},Y_{1}]$. Therefore, there is
at least one vertex of $X^{\prime\prime}$ say $x_{2}$, so that $|N_{G}(x)|=8$.
Otherwise, we have $|\cup_{i=2}^{i=6}N_{G}(x_{i})|\leq 35$ and the proof is
complete by Claim2.9. W.l.g assume that $Y_{2}=N_{G}(x_{2})\cap Y\setminus
Y_{1}$ and $|Y_{2}|=7$. Therefore, one can say that there is at least two
vertices of $X^{\prime\prime}\setminus\\{x_{2}\\}$ say $\\{x_{3},x_{4}\\}$, so
that for each $x\in\\{x_{3},x_{4}\\}$, we have $|N_{G}(x)\cap Y_{2}|=1$,
otherwise as $|Y_{2}|=7$ and $|N_{G}(x)\cap Y_{1}|\leq 1$ for each $x\in
X\setminus\\{x_{1}\\}$, then one can say that
$K_{6,6}\cong\overline{G}[X\setminus\\{x_{2}\\},Y_{2}]$. Now, one can check
that $|\cup_{i=1}^{i=5}N_{G}(x_{i})|\leq 9+7+6+6+7=35$, and the proof is
complete by Claim2.9.

Case 3. $\Delta=10$. W.l.g let $N_{G}(x_{1})=Y_{1}=\\{y_{1},\ldots,y_{10}\\}$.
Therefore by $K_{2,2}\nsubseteq G$ it is clear to say that
$K_{6,4}\subseteq\overline{G}[X\setminus\\{x_{1},x\\},Y_{1}]$ for each $x\in
X\setminus\\{x_{1}\\}$. Let there is a member of $X\setminus\\{x_{1}\\}$ say
$x_{2}$, so that $|N_{G}(x_{2})\cap(Y\setminus Y_{1})=Y_{2}|=8$. Therefore, as
$K_{2,2}\nsubseteq G$, we have $|N_{G}(x_{i})\cap Y_{2}|\leq 1$. Hence, since
$|Y_{2}|=8$ and $|X\setminus\\{x_{1},x_{2}\\}|=2$, one can say that
$K_{6,2}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{2}]$. So,
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}\cup Y_{2}]$.
Now, one can suppose that $|N_{G}(x)\cap(Y\setminus Y_{1})|\leq 7$ for any
member of $X\setminus\\{x_{1}\\}$. Hence:

######  Claim 2.14.

Suppose that $|Y^{\prime}=N_{G}(x)\cap(Y\setminus Y_{1})|=7$. If either
$|N_{G}(x^{\prime})\cap Y^{\prime}|=0$ for one $x^{\prime}\in
X\setminus\\{x_{1},x\\}$, or $|N_{G}(x^{\prime})\cap
N_{G}(x^{\prime\prime})\cap Y^{\prime}|=1$ for some
$x^{\prime},x^{\prime\prime}\in X\setminus\\{x_{1},x\\}$, then
$K_{6,6}\subseteq\overline{G}$.

###### Proof of Claim 2.14.

W.l.g let $|Y^{\prime}=N_{G}(x_{2})\cap(Y\setminus Y_{1})|=7$. Also, w.l.g let
$|N_{G}(x_{3})\cap Y^{\prime}|=0$. Therefore, Since $K_{2,2}\nsubseteq G$, so
$|N_{G}(x_{i})\cap(Y_{1}\cup Y^{\prime})|\leq 2$ for each
$i\in\\{3,4,5,6,7,8\\}$. As $|Y_{1}\cup Y^{\prime}|=17$, $|N_{G}(x_{3})\cap
Y^{\prime}|=0$, and $|N_{G}(x_{i})\cap Y_{1}\cup Y^{\prime}|\leq 2$, one can
say that $|\cup_{i=3}^{i=8}(N_{G}(x_{i})\cap Y_{1}\cup Y^{\prime})|\leq 11$,
which means that
$K_{6,6}\subseteq\overline{G}[X\setminus\\{x_{1},x_{2}\\},Y_{1}\cup Y_{2}]$.
For the case that $|N_{G}(x^{\prime})\cap N_{G}(x^{\prime\prime})\cap
Y^{\prime}|=1$ for some $x^{\prime},x^{\prime\prime}\in
X\setminus\\{x_{1},x\\}$, the proof is the same. Hence, the claim holds. ∎

Set $M$ as follow:

$M=\\{x\in X\setminus\\{x_{1}\\},~{}~{}|N_{G}(x)\cap(Y\setminus Y_{1})|=7\\}.$

By considering $M$, we have:

######  Claim 2.15.

If $|M|\neq 0$, then we have $K_{6,6}\subseteq\overline{G}$.

###### Proof of Claim 2.15.

W.l.g let $x_{2}\in M$, and $N_{G}(x_{2})\cap(Y\setminus
Y_{1})=Y_{2}=\\{y_{11},y_{12}\ldots,y_{17}\\}$. If $|M|\geq 5$, then by Claim
2.14, it can be said that $|\cup_{x_{j}\in M^{\prime}}N_{G}(x_{j})|\leq 35$,
where $M^{\prime}\subseteq M$ and $|M^{\prime}|=5$. Hence, the proof is
complete by Claim 2.9. Now, assume that $|M|=i$, and w.l.g suppose that
$M=\\{x_{2},x_{3},\ldots,x_{i+1}\\}$, where $i\in\\{1,2,3,4\\}$. Also if
$|M|\leq 2$, then it can be said that $|\cup_{x_{j}\in
M^{\prime\prime}}N_{G}(x_{j})|\leq 35$, where $M^{\prime\prime}\subseteq
X\setminus M$ and $|M^{\prime\prime}|=5$. Hence, the proof is complete by
Claim 2.9. Now assume that $|M|=i$, where $i\in\\{3,4\\}$.

By Claims 2.14, for the case that $i=4$, we have
$|\cup_{j=1}^{j=5}N_{G}(x_{j})|=10+7+6+5+4=32$. Hence, the proof is complete
by Claim 2.9. Also for the case that $i=3$, by Claims 2.14, we have
$|\cup_{j=1}^{j=4}N_{G}(x_{j})|=10+7+6+5=28$. Therefore, we have
$|\cup_{j=1}^{j=5}N_{G}(x_{j})|\leq 34$. Hence, the proof is complete by Claim
2.9.

∎

Now, by Claim 2.15, let $|M|=0$, that is $|N_{G}(x)\cap(Y\setminus Y_{1})|\leq
6$ for each $x\in X\setminus\\{x_{1}\\}$. In this case, the proof is complete
by Claim 2.9.

Hence, by Cases 1, 2, 3, the upper bound holds. Thus,
$BR_{8}(K_{2,2},K_{6,6})=45$ and theorem holds. ∎

###### Proof of Theorem 1.4.

By combining Theorems 2.2, 2.3, and 2.7, Theorem 1.4 is holds. ∎

## References

  * [1] Bi, Z., Chartrand, G., Zhang, P.: Another view of bipartite ramsey numbers.  Discussiones Mathematicae: Graph Theory 38(2) (2018)
  * [2] Bi, Z., Chartrand, G., Zhang, P.: A new view of bipartite ramsey numbers.  J. Combin. Math. Combin. Comput 108, 193–203 (2019)
  * [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] Goddard, W., Henning, M.A., Oellermann, O.R.: Bipartite ramsey numbers and zarankiewicz numbers.  Discrete Mathematics 219(1-3), 85–95 (2000)
  * [7] Goedgebeur, J., Van Overberghe, S.: New bounds for ramsey numbers r (kk- e, kl- e).  Discrete Applied Mathematics 307, 212–221 (2022)
  * [8] 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)
  * [9] Hattingh, J.H., Henning, M.A.: Star-path bipartite ramsey numbers.  Discrete Mathematics 185(1-3), 255–258 (1998)
  * [10] 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)
  * [11] Rowshan, Y.: The $m$-bipartite ramsey number $br\\_m(h\\_1,h\\_2)$.  arXiv preprint arXiv:2202.04921 (2022)
  * [12] Rowshan, Y.: The $m$-bipartite ramsey number $br_m(k_{2,2},k_{5,5})$ (2022)
  * [13] Rowshan, Y., Gholami, M.: Another view of Bipartite Ramsey numbers.  arXiv e-prints arXiv:2201.12844 (2022)
  * [14] Rowshan, Y., Gholami, M., Shateyi, S.: A proof of a conjecture on bipartite ramsey numbers b(2,2,3).  Mathematics 10(5) (2022).  DOI 10.3390/math10050701.  URL https://www.mdpi.com/2227-7390/10/5/701
  * [15] Wang, Y., Li, Y., Li, Y.: Bipartite ramsey numbers of kt, s in many colors.  Applied Mathematics and Computation 404, 126220 (2021)