% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf  All Ramsey numbers for brooms in graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Pei Yu \\%\thanks{Supported by NASA grant ABC123.}\\
\small Department of Mathematics\\[-0.8ex]
\small Tongji University\\[-0.8ex]
\small Shanghai, China\\
\small\tt yupeizjy@163.com\\
\and
Yusheng Li \qquad \\
\small Department of Mathematics\\[-0.8ex]
\small Tongji University\\[-0.8ex]
\small Shanghai, China\\
\small\tt li\_yusheng@tongji.edu.cn
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{July 17, 2015}{XX}\\
\small Mathematics Subject Classifications: 05D10}

\begin{document}

\maketitle

\begin{abstract}
  For $k,\ell\ge 1$, a broom $B_{k,\ell}$ is a tree on $n=k+\ell$ vertices obtained by connecting the central vertex of a star $K_{1,k}$ with an end-vertex of a path on $\ell-1$ vertices.  As $B_{n-2,2}$ is a star and $B_{1,n-1}$ is a path, their  Ramsey number have been determined among rarely known $R(T_n)$ of trees $T_n$ of order $n$.  Erd\H{o}s, Faudree, Rousseau and Schelp determined the value of  $R(B_{k,\ell})$ for $\ell\ge 2k\geq2$. We shall determine all other $R(B_{k,\ell})$ in this paper, which says that, for fixed $n$,  $R(B_{n-\ell,\ell})$ decreases first on $1\le\ell \le 2n/3$ from $2n-2$ or $2n-3$ to $\lceil\frac{4n}{3}\rceil-1$, and then it increases  on $2n/3 < \ell\leq n$ from $\lceil\frac{4n}{3}\rceil-1$ to $\lfloor\frac{3n}{2}\rfloor -1$. Hence $R(B_{n-\ell,\ell})$ may attain the maximum  and minimum values of $R(T_n)$ as $\ell$ varies.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Ramsey number; Tree; Broom
\end{abstract}

\section{Introduction}

Given a graph $G$, the {\em Ramsey number} $R(G)$ is the smallest integer $N$ such that every red-blue coloring of the edges of $K_N$ contains a monochromatic $G$.
Let $T_n$ be a tree of order $n$. Finding $R(T_n)$ for an arbitrary $T_n$  is a difficult unsolved problem in Ramsey theory. Most works focus on improving the known bounds, see \cite{Radziszowski}. Erd\H{o}s and S\'os conjectured that if a graph $G$ has average degree greater than $n-1$, then $G$ contains every tree of $n$ edges, which implies that $R(T_n)\le 2n-2$ for $n\ge 2$. A result of Erd\H{o}s, Faudree, Rousseau and Schelp in \cite{EFRS} yields

\begin{equation}\label{both-bounds}
r(T_n) \ge \Big\lceil\frac{4n}{3}\Big\rceil-1,
\end{equation}
under (\ref{lower-T}) by minimizing the lower bound with $b=2a$, and the lower bound can be attained by some brooms. For $k,\ell\ge 1$, a broom $B_{k,\ell}$ is a tree on $k+\ell$ vertices obtained by connecting the central vertex of a star $K_{1,k}$ with an end-vertex of a path on $\ell-1$ vertices. Thus $B_{k,1}=K_{1,k}$, $B_{k,2}=K_{1,k+1}$ and $B_{1,\ell}=P_{\ell+1}$, where $P_{\ell+1}$ is a path of order $\ell+1$. They obtained the following result.

\begin{theorem}(\cite{EFRS})\label{ef}
Let $k$ and $\ell$ be integers with $\ell\geq 2k\geq2$ and $n=k+\ell$. Then
\[
R(B_{k,\ell})=n+ \Big\lceil \frac{\ell}{2} \Big\rceil -1.
\]
\end{theorem}
Thus $R(B_{k,\ell})=\lceil\frac{4n}{3}\rceil -1$ for $\ell\in \{2k,2k+1,2k+2\}$ and $n=k+l$, which attain the lower bound in (\ref{both-bounds}). In this paper, we shall determine the values of $R(B_{k,\ell})$ for $ 1\le \ell\le 2k-1$.

Note that when $k$ is fixed and $\ell$ is sufficient large, $B_{k,\ell}$ is similar to a path $P_n$; when $\ell$ is fixed and $k$ is sufficient large, $B_{k,\ell}$ is similar to a star $K_{1,n-1}$. Among few known results of $R(T_n)$, $R(P_n)$ and $R(K_{1,n-1})$ have been determined completely. For $n\ge 2$, the exact value of $R(P_n)$ was determined in \cite{GG} as
\[
R(P_n)=\Big\lfloor\frac{3n}{2}\Big\rfloor -1,
\]
and $R(K_{1,n-1})$ was determined in \cite{CH} as
\[
R(K_{1,n-1})=\left\{ \begin{array}{ll}
                 2n-3 & \mbox{if \,$n$ is odd,}\\
                                  2n-2 & \mbox{otherwise.}
                                   \end{array}\right.
\]
As $B_{1,\ell}=P_{\ell+1}$, $B_{k,1}=K_{1,k}$ and $B_{k,2}=K_{1,k+1}$, their Ramsey numbers can be determined by the above results. It was proved that $R(B_{k,3})=R(K_{1,k+1})$ in \cite{BS}. Thus we shall consider the case $\ell\ge 4 $ and $k\geq 2$.


\begin{theorem}\label{main-th}
Let $k$ and $\ell$ be integers with $k\geq 2$ and $n=k+\ell$. Then
\[
R(B_{k,\ell})=\left\{\begin{array}{cc}
 n+ \lceil \frac{\ell}{2}\rceil -1 & \mbox{if\; $\ell\ge 2k-1$},\\
2n-2\lceil\frac{\ell}{2}\rceil -1 & \mbox{if\; $4\le \ell\le 2k-2$}.
                            \end{array}     \right.
\]
\end{theorem}

{\em Remark.} Roughly speaking, for fixed $n$, $R(B_{n-\ell,\ell})$ decreases first on $2\le\ell\le \frac{2n-1}{3}$ from $2n-2$ or $2n-3$ to $\lceil\frac{4n}{3}\rceil-1$, and then increases on $\frac{2n-1}{3}<\ell\leq n$ from $\lceil\frac{4n}{3}\rceil-1$ to $\lfloor\frac{3n}{2}\rfloor -1$. Hence $R(B_{n-\ell,\ell})$ may attain the maximum and minimum values of $R(T_n)$ when $\ell$ varies, as it is believed that $R(K_{1,n-1})$ is the maximum value of $R(T_n)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proofs}

For any red-blue edge-coloring of $K_{N}$, denote $R$ and $B$ be the induced red and blue subgraph, respectively, and $N_R(x)$ and $N_B(x)$ be the red neighborhood and blue neighborhood of $x$, respectively. Let $N_R[x]=N_R(x)\cup\{x\}$, $N_B[x]=N_B(x)\cup\{x\}$, $\deg_R(x)=|N_R(x)|$, and $\deg_B=|N_B(x)|$. For a graph $G$ and disjoint subset $A$ and $D$, denote by $G(A)$ the subgraph of $G$ induced by $A$, and $G(A,D)$ the bipartite subgraph of $G$ induced by $A$ and $D$. If $G$ is the red-blue edge-colored $K_N$, we write $G_R(A)=G(A)\cap R$ and $G_R(A,D)=G(A,D)\cap R$.
Notation not specifically mentioned will follow from \cite{Bollobas}. We do not distinguish the vertex set and the graph when there is no danger of confusion.

Consider a tree $T_n$ as a bipartite graph with two parts of size $a$ and $b$, respectively, where $a\leq b$, $a+b=n$. Observing that a red-blue edge-colored $K_{2a+b-2}$ with $R=K_{a-1}\cup K_{a+b-1}$ contains no monochromatic $T_n$, and a red-blue edge-colored $K_{2b-2}$ with $R=K_{b-1}\cup K_{b-1}$ contains no monochromatic $T_n$. We see that

\begin{equation}\label{lower-T}
R(T_n)\ge  \max\Big\{2a+b-1,\;2b-1\Big\},
\end{equation}
where $a$ and $b$ are determined by $T_n$.

Note that $B_{k,\ell}$ is a bipartite graphs on parts of sizes $a=\lceil \frac{\ell}{2}\rceil$ and $b=k+\lfloor \frac{\ell}{2}\rfloor$, then
 \begin{equation}\label{lower-b}
R(B_{k,\ell})\ge  \max\Big\{k+\Big\lceil \frac{3\ell}{2}\Big\rceil-1,\;2k+2\Big\lfloor\frac{\ell}{2}\Big\rfloor-1\Big\}.
\end{equation}

We shall prove the cases $\ell=2k-1$ and $\ell=4$ in Theorem \ref{main-th} via the following two lemmas.

\begin{lemma}\label{main-1}
Let $k\ge 2$ be an integer. Then
\[
R(B_{k,2k-1})=4k-2.
\]
\end{lemma}

\begin{lemma}\label{main-2}
Let $k\ge 2$ be an integer. Then
\[
R(B_{k,4})=2k+3
\]
\end{lemma}

In order to prove Lemma \ref{main-1}, we need two results from \cite{Jackson} and \cite{FS}, respectively.

\begin{lemma}\label{2kcycle}
(\cite{Jackson})
Let $G(A,D)$ be a bipartite graph on parts $A$ and $D$ with $|A|=k$ and $|D|=2k-2$ such that
\[
\min\{d(x):\;x\in A\}\ge k.
\]
Then $G(A,D)$ contains a cycle $C_{2k}$ .
\end{lemma}

\begin{lemma}\label{2k-cycle}
(\cite{FS})
$R(C_{2k})=3k-1$ for integer $k\ge 3$
\end{lemma}

\begin{proof}[Proof of Lemma \ref{main-1}]

It is easy to see that $R(B_{2,3})=6$, we assume that $k\ge 3$. As the lower bound (\ref{lower-b}) implies
$R(B_{k,2k-1})\geq 4k-2$, it suffices to show the opposite inequality.

Let $G$ be a red-blue edge-colored $K_{4k-2}$. We shall show that $G$ contains a monochromatic $B_{k,2k-1}$. By lemma
\ref{2k-cycle}, $G$ contains a monochromatic cycle $C_{2k}$. Without loss of generality, we assume that this $C_{2k}$ is blue and denote it by $C_{2k}^{(B)}$. Let $D=G\setminus C_{2k}^{(B)}$. Then $|D|=2k-2$.  If there exists a vertex $x\in C_{2k}^{(B)}$ such that $|N_{B}(x)\cap D|\ge k-1$, then $G$ contains a blue $B_{k,2k-1}$. We then assume that $|N_B(x)\cap D|\le k-2$ for each $x\in C_{2k}^{(B)}$. The fact that
\[
|N_B(x)\cap D|+|N_R(x)\cap D|=|D|=2k-2
\]
implies that $|N_{R}(x)\cap D|\ge k$ for each $x\in C_{2k}^{(B)}$, hence the number of red edges between $C_{2k}^{(B)}$ and $D$ is at least $2k^2$. So there exists a vertex $u\in D$ such that
\[
|N_{R}(u)\cap C_{2k}^{(B)}|\ge \frac{2k^2}{|D|}= \frac{2k^2}{2k-2}\geq k+1.
\]
Let $\{ u_{0},u_{1},\dots,u_{k}\}\subseteq N_{R}(u)\cap C_{2k}^{(B)}$, and $A=C_{2k}^{(B)}\setminus \{u_{1},u_{2},\dots,u_{k}\}$. Then $|A|=k$.
Consider the bipartite graph $G_R(A,D)$. By  Lemma \ref{2kcycle}, there is a red cycle $C_{2k}$ between $A$ and $D$. Denote by $C_{2k}^{(R)}$ the red $C_{2k}$. Since $C_{2k}^{(R)}$ contains $A$ hence $u_{0}$,
so the graph on $\{u_{1},u_{2},...,u_{k}\},u,u_0,C_{2k}^{(R)}$ induced by red edges contains a red $B_{k,2k-1}$.

  This completes the proof of Lemma \ref{main-1}.
\end{proof}

\begin{proof}[Proof of  Lemma \ref{main-2}.]

The lower bound (\ref{lower-b}) implies $R(B_{k,4})\ge 2k+3$, and we shall show $R(B_{k,4})\le 2k+3$. Let $G$ be a red-blue edge-colored  $K_{2k+3}$. Assume that $G$ contains no monochromatic $B_{k,4}$.

If $k=2$, $2k+3=7$.  As $R(P_5)=6<7$, we suppose that $G$ contain a red $P_5$. Label the vertices of the path in order as $\{x_1,x_2,...,x_5\}$, denote another two vertices as $y_1,y_2$. Since there is no red $B_{2,4}$, all the edges between $\{x_2,x_4\}$ and $\{y_1,y_2\}$ are red. If there is red edge between $\{x_1,x_5\}$ and $\{y_1,y_2\}$, say edge $x_5y_2$ is red.  Then edges $x_5y_1$, $x_3y_1$,$x_3y_2$ are blue. Now $\{x_2,x_3\},y_2,x_4,y_1,x_5$ contain a blue $B_{2,4}$, a contradiction. If all the edges between  $\{x_1,x_5\}$ and $\{y_1,y_2\}$ are blue, then $\{x_1,x_2\},y_2,x_4,y_1,x_5$ contain a blue $B_{2,4}$, a contradiction.

Now we consider the case $k\geq3$.
As $R(K_{1,k+1})< 2k+3$, we suppose that there is a blue star $K_{1,k+1}$, which is denoted by $K_{1,k+1}^{(B)}$. Let $x$ be the center of $K_{1,k+1}^{(B)}$, $A=K_{1,k+1}^{(B)}\setminus \{x\}$ and $D=G\setminus K_{1,k+1}^{(B)}$. Then $|A|=|D|=k+1$.

\medskip

{\bf Claim.}   $D$ induces a red $K_{k+1}$.

\textbf{Proof.} Suppose to the contrary, there is a blue edge $uv$ in $D$. Since $G$ contains no blue $B_{k,4}$, the edges between $\{u,v\}$ and $A$ are all red, and thus all the edges between $\{u,v\}$ and $D\setminus \{u,v\}$ are blue from the assumption that $G$ contains no red $B_{k,4}$. Now consider the blue edges between  $\{u,v\}$ and $A$.  With a similar analysis, we get that $D$ induces a blue $K_{k+1}$ and all edges between $D$ and $A$ are red.

Now, consider the adjacency between $x$ and a vertex of $D$, say $xu$, no matter what the color of $xu$ is, we have a monochromatic $B_{k,4}$, leading to a contradiction and the claim is proved. 

Now $D$ is a red $K_{k+1}$. If there exists a red edge $xw$ with $w\in D$, then $D\cup \{x\}$ induces a red $K_{1,k+1}$ with center $w$. As $A=V(G)\setminus(D\cup \{x\})$, a similar analysis for the above claim tells us that $A$ is a blue $K_{k+1}$. If the number of blue edges between $A$ and $D$ is at least $k+2$, then there exists a vertex $y\in A$  such that $|N_{B}(y)\cap D|\geq 2$. Now choose two vertices $\{y_1,y_2\}\subseteq N_{B}(y)\cap D$ and two vertices $\{a_1,a_2\}\subseteq A\setminus y$, then  $(A\setminus\{a_1,a_2,y\})\cup\{y_1,y_2\},y,a_1,a_2,x$ contains a blue $B_{k,4}$, a contradiction. Thus assume to the contrary, there exists a vertex $z\in D$ such that $|N_{R}(z)\cap A|\geq \frac{(k+1)^{2}-(k+1)}{|D|}=k\ge 2$.  If $w,z$  are the same vertex, we can choose two vertices $\{z_1,z_2\}\subseteq N_{R}(z)\cap A$ and three vertices $\{d_1,d_2,d_3\}\subseteq D\setminus z$ for $|D|=k+1\geq 4$. Then $(D\setminus\{d_1,d_2,d_3,z\})\cup\{z_1,z_2,x\},z,d_1,d_2,d_3$ contain a red $B_{k,4}$. If $w,z$ are different, choose a vertex $d_1\in D\setminus \{z,w\}$, then $(D\setminus\ \{z,w,d_1\})\cup\{z_1,z_2\},z,d_1,w,x$ contain a red $B_{k,4}$, a contradiction.

Finally, assume that $x$ is adjacent to $D$ completely blue.  Choose any set $F\subseteq A\cup D$ such that $|F|=k+1$ and denote $M=V(G)\setminus (F\cup x)$. A similar analysis for the claim says that $M$ is a red $K_{k+1}$. The choice of $F$ tells us that  $A\cup D$ is a red $K_{2k+2}$, hence G contains a red $B_{k,4}$, which is a contradiction too.

 This completes the proof of Lemma \ref{main-2}..
\end{proof}

\begin{lemma}\label{yz}
For integers $k,\ell,N$ with $5\le \ell \leq 2k-2$ and $N\ge 2k+2\lfloor \frac{\ell}{2}\rfloor-1$, let the edges of $K_N$ be colored by two colors  $i\equiv 0,1\pmod{2}$. Suppose $i$ is a color and $x$  is a vertex such that
\[
\deg_i(x)=\max_{v}\max \{\deg_i(v),\;\deg_{i+1}(v)\}.
\]
If there exist vertices $y,z \subseteq N_{i+1}(x)$, not necessarily distinct, satisfying
 \begin{enumerate}
  \item  $|N_{i+1}(y)\cap N_{i}(x)|\ge k$, and
  \item  $\deg_{i+1}(z) \ge N-\ell$
    \end{enumerate}
then $G$ contains a monochromatic $B_{k,\ell}$.
 \end{lemma}

\begin{proof}[Proof of  Lemma \ref{yz}.]
 Since $|N_{i+1}(y)\cap N_{i}(x)|\geq k$, we can choose a subset $A$ in $N_{i+1}(y)\cap N_{i}(x)$ such that $|A|=k$. Let $H=G\setminus A$, then $|H|=N-k$. Since $R(C_{2t})=3t-1$ for $t\ge 3$, $H$ contains a monochromatic $C_{2t}$ in color $j$, denoted by $C_{2t}^{(j)}$, where
\[
2t\geq 2 \Big\lfloor\frac{N-k+1}{3}\Big\rfloor \ge 2\Big\lfloor\frac{k+2\lfloor \ell/2 \rfloor}{3}\Big\rfloor\ge \ell
\]
for $5\le \ell \leq 2k-2$. The choice of vertex $x$ implies $\deg_i(x) \ge \deg_{i+1}(z)\ge  N-\ell$, and thus
\[
\Big|N_{i}[x]\setminus A\Big|+\Big|C_{2t}^{(j)}\Big|\ge |H|+1, \hspace{5mm} \Big|N_{i+1}[z]\setminus A\Big|+\Big|C_{2t}^{(j)}\Big|\ge |H|+1,
\]
which implies that both $N_{i}[x]\setminus A$ and $ N_{i+1}[z]\setminus A$ contain a vertex of $C_{2t}^{(j)}$.

{\em Case 1.} $y=z$. If $j=i $, namely, $C_{2t}^{(j)}=C_{2t}^{(i)}$ is in color $i$, there is a monochromatic $B_{k,\ell}$ in color $i$ in $A\cup\{x\} \cup C_{2t}^{(i)}$, and otherwise $j=i+1$, there exists a monochromatic $B_{k,\ell}$ in color $i+1$ in $A\cup \{y\}\cup C_{2t}^{(i+1)}$.

{\em Case 2.} $y\neq z$. Similarly, we can find a monochromatic $B_{k,\ell}$ either in $A\cup\{x\} \cup C_{2t}^{(j)}$ or in $A\cup \{y,x,z\}\cup C_{2k}^{(j)}$.

 This completes the proof of Lemma \ref{yz}.
\end{proof}

\medskip



The next two lemmas are results about the extremal edges in  graph that contains no path $P_{t}$.

\begin{lemma}\label{le-path} (\cite{EG})
Let $t\geq 2$ be an integer, and  $G$  a graph of order $N$ that contains no $P_{t}$. Let $e(G)$ be the number of edges of $G$, then $e(G)\leq \frac{(t-2) N}{2}$.
\end{lemma}

\begin{lemma}\label{Gya} (\cite{GRS})
Let $G(X_B,X_R)$ be a bipartite graph on parts $X_B$ and $X_R$ with $|X_R| \le |X_B|$. If $G(X_B,X_R)$ contains no $P_{2t}$ with $2(t-1)\le |X_R|$, then
\[
e(G(X_B,X_R))\le (t-1)\Big[|X_B|+|X_R|-2(t-1)\Big].
\]
\end{lemma}

\begin{proof}[Proof of Theorem \ref{main-th}]

We may assume that $5\le\ell\le 2k-2$ from Theorem \ref{ef}, Lemma \ref{main-1} and Lemma \ref{main-2}.

Set $N=2n-2\lceil\frac{\ell}{2}\rceil-1=2k+2\lfloor\frac{\ell}{2}\rfloor-1$. Let $G$ be a red-blue edge-colored  $K_N$, and let $R$ and $B$ be the induced red and blue subgraph, respectively. Without loss of generality, we may assume that the maximal monochromatic degree of $G$ is the maximum blue degree  and $x$ is a vertex such that
\[
\deg_B(x)=\max_{v}\max \{\deg_B(v),\;\deg_R(v)\}.
\]
To simplify the notation, we write $X_B=N_{B}(x)$, $X_R=N_{R}(x)$ and
\[
t=\ell+k-|X_B|-1.
\]
The choice of $x$ implies $N_{B}(u)\cap X_B \neq \emptyset$ for each vertex $u\in X_R$ as otherwise $N_B[x]\subseteq N_R(u)$ and thus $\deg_R(u)>\deg_B(x)$, which is impossible. We shall separate the proof into three cases depending on $|X_B|$.

\medskip

{\em Case 1.} $|X_B|< k+\ell-1$, and either $G(X_R)$ contains a blue $P_{t}$, denoted by $P_t^{(B)}$, or $G(X_B,X_R)$ contains a blue $P_{2t}$, denoted $P_{2t}^{(B)}$.

In $G(X_B \cup X_R)$, let $P^{(B)}$ be the longest blue path extended from $P_t^{(B)}$  such that one of its end-vertices is in $X_B$ if $G(X_R)$ contains a blue $P_{t}$, or that from $P_{2t}^{(B)}$ otherwise.  If $|P^{(B)}|\ge \ell-1$, then there exists a blue $B_{k,\ell}$. Thus we assume that $|P^{(B)}|\le \ell-2$, then $P^{(B)}$ fails to contain at least $|X_B|-(\ell-2-t)=k+1$ vertices of $X_B$. Let $y$ be the other end-vertex of $P^{(B)}$. Then $|N_R(y)\cap X_B| \ge k+1$. The maximality of $|P^{(B)}|$ implies $|N_R(y)|\ge N-1-(\ell-2)=N-\ell+1$, which and Lemma \ref{yz} imply that $G$ contains a monochromatic $B_{k,\ell}$.

\medskip

{\em Case 2.}  $|X_B|\geq k+\ell-1$.

Let $P^{(B)}$ be the longest blue path in $G(X_B\cup X_R)$ that has an end-vertex in $X_B$. A similar analysis in Case 1 implies that $G$ contains a monochromatic $B_{k,\ell}$.

\medskip

{\em Case 3.} $|X_B|<k+\ell-1$, and neither $G(X_R)$ contains a blue $P_t$ nor $G(X_B,X_R)$ contains a blue $P_{2t}$.

As $t=\ell+k-|X_B|-1\geq 2$, then $|X_B|\leq \ell+k-3$ and $|X_R|=N-1-|X_B|\geq k$.

Since $G(X_R)$ contains no blue $P_t$, Lemma \ref{le-path} implies $e(G_B(X_R))\le (t-2)|X_R|/2$. The choice of $x$ implies that the $\min\{\deg_R(v),\;\deg_B(v)\}\ge |X_R|$ for each vertex $v$ of $G$, and thus
\[
e(G_B(X_B,X_R)) \ge |X_R|\cdot|X_R|-(t-2)|X_R|=(|X_R|-t+2)|X_R|.
\]
Since $G(X_B,X_R)$ contains no blue $P_{2t}$, Lemma \ref{Gya} yields
\[
e(G_B(X_B,X_R))\le M_B,
\]
where
\[
M_B= (t-1)\Big[|X_{B}|+|X_{R}|-2(t-1)\Big].
\]

\medskip

{\bf Claim for Case 3.}  $G(X_B,X_R)$ has at most $|X_R|(|X_B-k|)-1$ blue edges.

{\bf Proof.} Suppose opposite, then
\[
e(G_B(X_B,X_R)) \ge |X_R|\cdot \max\{|X_R|-t+2,|X_B|-k\}\ge m_B.
\]
where
\[
m_B = k(|X_R|-t+2)+(|X_R|-k)(|X_B|-k).
\]
Note that $M_B$ and $m_B$ are upper and lower bound of number of blue edges in $G(X_B,X_R)$, respectively, and thus $M_B\ge m_B$.

{\em Case 3.1.} $\ell$ is even.  In this subcase, $|X_B|+|X_R| =2k+\ell-2$ and
\begin{align*}
    &t=\ell+k-|X_B|-1=|X_R|-k+1,\\
    &m_B=  k(k+1)+(|X_R|-k)(|X_B|-k),\\
    &M_B= (|X_R|-k)\Big[|X_B|+k-(|X_R|-k)\Big]
\end{align*}
we have
\[
m_B-M_B =k^{2}-2k(|X_R|-k)+(|X_R|-k)^{2}+k=(2k-|X_R|)^{2}+k>0,
\]
which is a contradiction.

\medskip

{\em Case 3.2.} $\ell$ is odd. In this subcase, $|X_R|+|X_B|=2k+\ell-3$ and
\begin{align*}
& t=\ell+k-|X_B|-1=|X_R|-k+2, \\
& m_B=k^{2}+(|X_R|-k)(|X_B|-k), \\
& M_B=(|X_R|-k+1)\Big[|X_B|+k-(|X_R|-k)-2\Big].
\end{align*}

We have
\begin{eqnarray*}
m_B-M_B & = & (2k-|X_R|)^{2}+3|X_R|-|X_B|-4k+2 \\
  & = & (2k-|X_R|)(2k-|X_R|-4)+2k-\ell+5.
\end{eqnarray*}

For $\ell\leq 2k-2$,is odd, we get $|X_R|\leq \lfloor\frac{N-1}{2}\rfloor\leq 2k-3$. If $|X_R|\leq 2k-4$, $m_B-M_B \ge 2k-\ell+5> 0$; if $\ell_{2}=2k-3$, $m_B-M_B=2k-\ell+2>0$, a contradiction, hence the claim holds.

\medskip

We now have
\[
e(G_R(X_R)) \ge \binom{|X_R|}{{2} }-\frac{(t-2)|X_R|}{2}\geq \frac{(k-1)|X_R|}{2}.
\]
and
\[
e((G_R(X_B,X_R)) \ge |X_R|\cdot|X_B|-\big[|X_R|(|X_B|-k)-1\big]=k|X_R|+1,
\]
Recall $X_R=N_{R}(x)$, and thus
\[
\sum_{v\in X_R}|N_{R}(v)| \ge e(G_R(X_B,X_R))+2 e(G_R(X_R))+|X_R|=2k|X_R|+1.
\]
Therefore, there exist $y,z\subseteq X_R=N_R(x)$,not necessarily distinct, such that $|N_{R}(y)\cap N_B(x)|\ge k+1$ and $|N_{R}(z)|\ge 2k+1\ge N-\ell$. Then, Lemma \ref{yz} implies that $G$ contains a monochromatic $B_{k,\ell}$.

 This completes the proof of Theorem~\ref{main-th}.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}

The authors are grateful to the editors and referees for their invaluable comments and suggestions, particularly, their careful reading and detailed marking on the manuscript.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{Bollobas}
B. Bollob\'as. \newblock {\em Modern Graph Theory}. \newblock Springer-Verlag, New York, 1998.
\bibitem{BS}
P. Bahls and T. Spencer. \newblock On the Ramsey numbers of trees with small diameter. \newblock {\em Graphs Combin.}, 29:39--44, 2013.
\bibitem{CH}
V. Chv{\'a}tal and F. Harary. \newblock Generalized Ramsey theory for graphs II, Small diagonal numbers. \newblock {\em Proc. Amer. Math. Soc.}, 32:389--394, 1972.
\bibitem{EFRS}
P. Erd\H{o}s, R. Faudree, C. Rousseau and R. Schelp. \newblock Ramsey numbers for brooms. \newblock {\em Congr. Numer.}, 35:283--293, 1982.
\bibitem{EG}
P. Erd\H{o}s and T.Gallai. \newblock On maximal paths and circuits graphs. \newblock {\em Acta Math. Acad. Sci. Hung.}, 10: 337--356, 1959.
\bibitem{FS}
R. Faudree and R. Schelp. \newblock All Ramsey numbers for cycles in graphs. \newblock {\em Discrete Math.}, 8:35--52,1974.
\bibitem{GG}
L. Ger{\'e}ncser and A. Gy{\'a}rfas. \newblock On Ramsey-type problems. \newblock {\em Ann. Univ. Sci. Budapest, E{\"o}tv{\"o}s Sect. Math.}, 10:167--170, 1967.
\bibitem{GRS}
A. Gy{\'a}rf{\'a}s, C. Rousseau and R. Schelp. \newblock An extremal problem for paths in bipartite graphs, \newblock {\em J. Graph Theory.}, 8:83--95, 1984.
\bibitem{Jackson}
B. Jackson. \newblock Cycles in bipartite graphs. \newblock {\em J. Combin. Theory Ser.B.}, 30:332--342, 1981.
\bibitem{Radziszowski}
S. Radziszowski.\newblock Small Ramsey numbers. \newblock {\em Electronic J. Combin.}, 1, 1994, a dynamic survey.

\end{thebibliography}

\end{document}
