% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.29}{23(3)}{2016} % 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{Jul 17, 2015}{Aug 2, 2016}{Aug 19, 2016}\\ \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},\ldots,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,\ldots,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|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}{99} \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.}, \#DS1 1994. \end{thebibliography} \end{document}