Long Paths in Bipartite Graphs and Path-Bistar Bipartite Ramsey Numbers

Abstract

In this paper, we focus on a so-called Fan-type condition assuring us the existence of long paths in bipartite graphs. As a consequence of our main result, we completely determine the bipartite Ramsey numbers $b(P_{s},B_{t_{1},t_{2}})$, where $B_{t_{1},t_{2}}$ is the graph obtained from a $t_{1}$-star and a $t_{2}$-star by joining their centers.

1 Introduction

In this paper, we consider only finite undirected simple graphs. Let G be a graph. We let V(G) and E(G) denote the vertex set and the edge set of G, respectively. For $x\in V(G)$, we let $N_{G}(x)$ and $d_{G}(x)$ denote the neighborhood and the degree of x, respectively; thus $N_{G}(x)=\{y\in V(G):xy\in E(G)\}$ and $d_{G}(x)=|N_{G}(x)|$. For $X\subseteq V(G)$, we let G[X] denote the subgraph of G induced by X. For two graphs G and H, we write $H\subset G$ if G contains H as a subgraph. Let $P_{n}$ and $K_{n_{1},n_{2}}$ denote the path of order n and the complete bipartite graph with partite sets having cardinalities $n_{1}$ and $n_{2}$, respectively. For terms and symbols not defined here, we refer the reader to [3].

Our main target in this paper is the bipartite Ramsey number. Let $H^{r}$ and $H^{b}$ be bipartite graphs. The following fact is obtained by similar argument in the original Ramsey’s theorem: there exists a positive integer N such that for any edge-disjoint spanning subgraphs $G^{r}$ and $G^{b}$ of $K_{N,N}$ with $E(G^{r})\cup E(G^{b})=E(K_{N,N})$, $H^{r}\subset G^{r}$ or $H^{b}\subset G^{b}$. The smallest value of N satisfying the above property is called the bipartite Ramsey number with respect to $H^{r}$ and $H^{b}$ and denoted by $b(H^{r},H^{b})$. Note that $b(H^{r},H^{b})=b(H^{b},H^{r})$.

If $H^{b}$ is a star, then the determination problem of $b(H^{r},H^{b})$ is reduced to a problem of finding $H^{r}$ under a high minimum degree condition. Thus the bipartite Ramsey numbers involving stars tend to be simply determined. For example, Harary et al. [6] proved that $b(K_{1,s},K_{1,t})=s+t-1$ and Hattingh and Henning [7] completely determined the value $b(P_{s},K_{1,t})$ for $s\ge 2$ and $t\ge 2$. Further results for the bipartite Ramsey number related to stars were given in [2, 12].

In Graph Theory, many types of degree conditions were studied for some important properties. We explain it with the Hamiltonicity of graphs as an example. Dirac [4] proved that if a graph G of order $n\ge 3$ satisfies $d_{G}(x)\ge \frac{n}{2}$ for all $x\in V(G)$, then G is Hamiltonian. This result influenced sufficient conditions for the existence of a Hamiltonian cycle with many extensions, for example, degree-sum condition, neighborhood-union condition, and so on (see a survey [9]). One of important extensions is a so-called Fan-type condition. Fan [5] proved that if a 2-connected graph G of order n satisfies

$$\begin{aligned} \max \{d_{G}(x),d_{G}(y)\}\ge \frac{n}{2}\quad \text{ for } \text{ all } x,y\in V(G) \text{ with } \mathrm{dist}_{G}(x,y)=2, \end{aligned}$$

where $\mathrm{dist}_{G}(x,y)$ is the distance between x and y, then G is Hamiltonian, and the result straightforward leads to Dirac’s result. In Graph Theory, similar situations occur, i.e., a minimum degree condition is frequently replaced by a Fan-type condition, that is a condition concerning $\max \{d_{G}(x),d_{G}(y)\}$ for non-adjacent vertices x and y (see, for example [10, 11, 13]).

We carry the concept to bipartite graphs. As we mentioned above, some bipartite Ramsey numbers involving stars are determined using a high minimum degree condition problem. We will later show that a Fan-type condition gives manageable objects which can be replaced by stars. From such a motivation, we study a Fan-type condition for long paths in bipartite graphs. The following is one of our main results.

Theorem 1

Letm andn be positive integers with$n\ge m$. LetG be a bipartite graph having partite sets$X_{1}$ and$X_{2}$ with$|X_{1}|=|X_{2}|=n$. If

(D1):

$\max \{d_{G}(x_{1}),d_{G}(x_{2})\}\ge m$ or

(D2):

$\min \{d_{G}(x_{1}),d_{G}(x_{2})\}\ge \frac{n+1}{2}$

for all vertices$x_{1}\in X_{1}$ and$x_{2}\in X_{2}$ with$x_{1}x_{2}\notin E(G)$, thenG contains a pathP with $|V(P)|\ge 2m$.

The condition (D1) in Theorem 1is best possible because $G=K_{n,n}-E(K_{m-1,m-1}\cup K_{n-m+1,n-m+1})$ satisfies $\max \{d_{G}(x_{1}),d_{G}(x_{2})\}\ge m-1$ for all vertices $x_{1}\in X_{1}$ and $x_{2}\in X_{2}$ with $x_{1}x_{2}\notin E(G)$, and any paths of G have at most $2m-1$ vertices.

Let $n_{1}$ and $n_{2}$ be non-negative integers, and let $S_{1}$ and $S_{2}$ be two vertex-disjoint stars having $n_{1}+1$ vertices and $n_{2}+1$ vertices, respectively. The $(n_{1},n_{2})$-bistar, denoted by $B_{n_{1},n_{2}}$, is the graph obtained from $S_{1}$ and $S_{2}$ by joining their centers. Note that the $(n_{1},0)$-bistar is the star having $n_{1}+2$ vertices and the (0, 0)-bistar is the connected graph of order two. Recently, Hattingh and Joubert [8] proved that $b(B_{s,s},B_{t,t})=s+t+1$, and Alm et al. [1] extended the result as $b(B_{s_{1},s_{2}},B_{t_{1},t_{2}})=s_{1}+t_{1}+1$ for $s_{1}\ge s_{2}$ and $t_{1}\ge t_{2}$. In particular, we obtain $b(K_{1,s},K_{1,t})=b(B_{s-1,s-1},B_{t-1,t-1})$. Hence the bipartite Ramsey number involving bistars seems to be related to one involving stars.

Recall that $b(P_{s},K_{1,t+1})~(=b(P_{s},B_{t,0}))$ was determined by Hattingh and Henning [7]. In this paper, using Theorem 1, we extend their result and determine the value $b(P_{s},B_{t_{1},t_{2}})$ as following.

Theorem 2

Lets, $t_{1}$ and$t_{2}$ be integers with$s\ge 2$ and$t_{1}\ge t_{2}\ge 0$. Then the following hold.

• (i) If$t_{1}=t_{2}$, then$b(P_{s},B_{t_{1},t_{2}})=\lfloor \frac{s-1}{2}\rfloor +t_{1}+1$.

• (ii) Assume that$t_{1}>t_{2}$.

  • (ii-a) If$t_{1}\ge \lfloor \frac{s-1}{2}\rfloor$, then

    $$\begin{aligned} b(P_{s},B_{t_{1},t_{2}})= {\left\{ \begin{array}{ll} \lfloor \frac{s-1}{2}\rfloor +t_{1}+1 &{} \left(s \text{ is } \text{ even, } \text{ or } s \text{ is } \text{ odd } \text{ and } t_{1}\equiv 0~\left( \text{ mod } \frac{s-1}{2}\right) \right)\\ \lfloor \frac{s-1}{2}\rfloor +t_{1} &{} (\text{ otherwise }). \end{array}\right. } \end{aligned}$$

  • (ii-b) If $t_{1}<\lfloor \frac{s-1}{2}\rfloor$, then

    $$\begin{aligned} b(P_{s},B_{t_{1},t_{2}})= {\left\{ \begin{array}{ll} 2t_{1}+1 &{} \left(2t_{1}-t_{2}\ge \lfloor \frac{s-1}{2} \rfloor \right)\\ \lfloor \frac{s-1}{2}\rfloor +t_{2}+1 &{} (\text{ otherwise }). \end{array}\right. } \end{aligned}$$

2 Proof of Theorem 1

We start with two lemmas. The following lemma is well-known (see, for example [7]).

Lemma 1

Letm be a positive integer, and letG be a bipartite graph. If$d_{G}(x)\ge m$ for all$x\in V(G)$, thenG contains a pathP such that$|V(P)|\ge 2m$.

Lemma 2

Letm be a positive integer. LetG be a connected bipartite graph having partite sets$X_{1}$ and$X_{2}$ with$|X_{1}|\ge |X_{2}|$, and let$x_{1}\in X_{1}$. If$d_{G}(x)\ge m$ for all$x\in X_{1}$, thenG contains a pathP such that $x_{1}$is an end-vertex ofP and$|V(P)|\ge 2m$.

Proof

We proceed by induction on m. It is clear that the lemma holds for $m=1$. Thus we may assume that $m\ge 2$.

Let $H_{0}=G-\{x_{1},y:y\in N_{G}(x_{1}),~d_{G}(y)=1\}$. Since $|V(H_{0})|\ge |X_{1}-\{x_{1}\}|\ge |X_{2}|-1\ge d_{G}(x_{1})-1\ge m-1\ge 1$, $H_{0}$ is non-empty. Since $|V(H_{0})\cap X_{1}|=|X_{1}|-1\ge |X_{2}|-1\ge |V(H_{0})\cap X_{2}|-1$, there exists a component $H_{1}$ of $H_{0}$ such that $|V(H_{1})\cap X_{1}|\ge |V(H_{1})\cap X_{2}|-1$. Since G is connected, it follows from the definition of $H_{0}$ that there exists a vertex $x_{2}\in N_{G}(x_{1})\cap V(H_{1})$ and $|V(H_{1})|\ge 2$.

Since $|V(H_{1}-x_{2})\cap X_{1}|=|V(H_{1})\cap X_{1}|\ge |V(H_{1})\cap X_{2}|-1=(|V(H_{1}-x_{2})\cap X_{2}|+1)-1$, there exists a component $H_{2}$ of $H_{1}-x_{2}$ such that $|V(H_{2})\cap X_{1}|\ge |V(H_{2})\cap X_{2}|$. Since $d_{G}(x_{2})\ge 2$, there exists a vertex $x_{3}\in N_{G}(x_{2})\cap V(H_{2})$. Note that $x_{3}\in X_{1}$ and $d_{H_{2}}(x)=d_{G}(x)-|N_{G}(x)-V(H_{2})|\ge m-|N_{G}(x)\cap \{x_{2}\}|\ge m-1$ for all $x\in V(H_{2})\cap X_{1}$. By the induction hypothesis, $H_{2}$ contains a path Q such that $x_{3}$ is an end-vertex of Q and $|V(Q)|\ge 2(m-1)$. Then the path $P=x_{1}x_{2}x_{3}Q$ is a desired path. $\square$

Proof of Theorem 1

Let m, n, G, $X_{1}$ and $X_{2}$ be as in Theorem 1. By way of contradiction, suppose that every path of G has at most $2m-1$ vertices. Let $P=y_{1}y_{2}\cdots y_{l}$ be a longest path of G. Then $l\le 2m-1$. Note that $V(G)-V(P)\ne \emptyset$ because $|V(G)|=2n\ge 2m$. Without loss of generality, we may assume that $y_{1}\in X_{1}$.

Since P is a longest path, all neighbors of $y_1$ are contained in $V(P) \cap X_2$. So, if $d_G(y_1) \ge m$, then $|V(P)| = |V(P) \cap X_1| + |V(P) \cap X_2| \ge 2 |V(P) \cap X_2| \ge 2 d_G(y_1) \ge 2m$, a contradiction. Thus, we have $d_G(y_1) \le m-1$.

Suppose that there exists a vertex $u \in X_2 - V(P)$ such that (D2) $\min \{d_G(y_1), d_G(u)\} \ge \frac{n+1}{2}$ holds. Let $I_{1}=\{1\le i\le \frac{l}{2}:y_{1}y_{2i}\in E(G)\}$ and $I_{2}=\{1\le i\le \frac{l}{2}:uy_{2i-1}\in E(G)\}$. Note that $|I_{1}|=d_{G}(y_{1})\ge \frac{n+1}{2}$ and since $y_l$ is not a neighbor of u, $|I_{2}| = d_{G}(u) - d_{G - V(P)}(u) \ge \frac{n+1}{2} - |X_1 - V(P)|$. Thus,

$$\begin{aligned} n - |X_1 - V(P)|= & {} |X_1 \cap V(P)| \ge \frac{l}{2} \ge |I_{1}\cup I_{2}|\\= & {} |I_{1}|+|I_{2}|-|I_{1}\cap I_{2}| \ge n\\&+1 - |X_1 - V(P)| -|I_{1}\cap I_{2}|. \end{aligned}$$

This implies $I_{1}\cap I_{2}\ne \emptyset$, say $i\in I_{1}\cap I_{2}$. Then $y_{l}y_{l-1}\cdots y_{2i}y_{1}y_{2}\cdots y_{2i-1}u$ is a path longer than P, a contradiction.

Therefore, for $u \in X_2 - V(P)$, (D1) $\max \{d_G(y_1), d_G(u)\} \ge m$ holds. Since $d_G(y_1) \le m-1$, we have $d_G(u) \ge m$ for $u \in X_2 - V(P)$. Since $|X_{1}|=|X_{2}|$ and $|V(P)\cap X_{1}|\ge |V(P)\cap X_{2}|$, there exists a component $H_{0}$ of $G-V(P)$ such that $|V(H_{0})\cap X_{2}|\ge |V(H_{0})\cap X_{1}|$. Let $h=\max \big \{|N_{G}(u)\cap V(P)|:u\in V(H_{0})\cap X_{2}\big \}$. Take a vertex $u^{*}\in V(H_{0})\cap X_{2}$ so that $|N_{G}(u^{*})\cap V(P)|=h$. Since $|V(P)\cap X_{1}|\le \frac{l+1}{2}\le \frac{2m}{2}$ and $u^{*}y_1\notin E(G)$, we have $0\le h\le m-1$. For $u\in V(H_{0})\cap X_{2}$, since $d_G(u) \ge m$,

$$\begin{aligned} d_{H_{0}}(u)=d_{G}(u)-|N_{G}(u)\cap V(P)|\ge m-h~(\ge 1). \end{aligned}$$

Then by Lemma 2, there exists a path $P'$ of $H_{0}$ such that $u^{*}$ is an end-vertex of $P'$ and $|V(P')|\ge 2(m-h)$. If $h=0$, then $|V(P')|\ge 2m$, which is a contradiction. Thus $h\ge 1$.

Note that $N_{G}(u^{*})\cap V(P)\subseteq V(P) \cap (X_{1}-\{y_1\})~(=\{y_{2j-1}:j\ge 2\})$. Let j be the maximum integer satisfying $u^{*}y_{2j-1}\in E(G)$. Since $|N_{G}(u^{*})\cap V(P)|=h$, we have $j\ge h+1$. Let $P''$ be the path as $P''=y_1Py_{2j-1}u^{*}P'$. Then $|V(P'')|\ge (2j-1)+2(m-h)\ge (2(h+1)-1)+2(m-h)>2m$, which is a contradiction. This completes the proof of Theorem 1. $\square$

3 Proof of Theorem 2

In this section, we prove Theorem 2. We first give several supporting lemmas.

Lemma 3

LetN be a positive integer, and let$t_{1}$ and$t_{2}$ be non-negative integers with$N\ge t_{1}\ge t_{2}$. Let$X_{1}$ and$X_{2}$ be the partite sets of$K_{N,N}$. Let$G^{r}$ and$G^{b}$ be edge-disjoint spanning subgraphs of$K_{N,N}$ with$E(G^{r})\cup E(G^{b})=E(K_{N,N})$. If$B_{t_{1},t_{2}}\not \subset G^{b}$, then

(N1):

$\max \{d_{G^{r}}(x_{1}),d_{G^{r}}(x_{2})\}\ge N-t_{2}$ or

(N2):

$\min \{d_{G^{r}}(x_{1}),d_{G^{r}}(x_{2})\}\ge N-t_{1}$

for all vertices$x_{1}\in X_{1}$ and$x_{2}\in X_{2}$ such that$x_{1}x_{2}\notin E(G^{r})$.

Proof

Let $x_{1}\in X_{1}$ and $x_{2}\in X_{2}$ be vertices such that $x_{1}x_{2}\notin E(G^{r})$. Since $B_{t_{1},t_{2}}\not \subset G^{b}$, $d_{G^{b}}(x_{1})\le t_{j}$ or $d_{G^{b}}(x_{2})\le t_{3-j}$ for each $j\in \{1,2\}$. Since $d_{G^{r}}(x_{i})+d_{G^{b}}(x_{i})=N$, this implies that

$$\begin{aligned} {d_{G^{r}}(x_{1})\ge N-t_{j}~ \hbox {or}~ d_{G^{r}}(x_{2})\ge N-t_{3-j}~\quad ~\hbox {for each}~~j\in \{1,2\}.} \end{aligned}$$

(1)

If $d_{G^{r}}(x_{1})\ge N-t_{2}$ or $d_{G^{r}}(x_{2})\ge N-t_{2}$, then (N1) holds. Thus we may assume that $d_{G^{r}}(x_{1})<N-t_{2}$ and $d_{G^{r}}(x_{2})<N-t_{2}$. Then by (1), we have $d_{G^{r}}(x_{1})\ge N-t_{1}$ and $d_{G^{r}}(x_{2})\ge N-t_{1}$, which implies (N2). $\square$

Lemma 4

Lets be an integer with$s\ge 2$, and let$t_{1}$ and$t_{2}$ be non-negative integers with$t_{1}\ge t_{2}$. Then$b(P_{s},B_{t_{1},t_{2}})\le \lfloor \frac{s-1}{2}\rfloor +t_{1}+1$.

Proof

Let $N=\lfloor \frac{s-1}{2}\rfloor +t_{1}+1$. Let $X_{1}$ and $X_{2}$ be the partite sets of $K_{N,N}$. Let $G^{r}$ and $G^{b}$ be edge-disjoint spanning subgraphs of $K_{N,N}$ with $E(G^{r})\cup E(G^{b})=E(K_{N,N})$. Suppose that $B_{t_{1},t_{2}}\not \subset G^{b}$. It suffices to show that $P_{s}\subset G^{r}$. Since $t_{1}\ge t_{2}$, it follows from Lemma 3 that $\max \{d_{G^{r}}(x_{1}),d_{G^{r}}(x_{2})\}\ge N-t_{1}=\lfloor \frac{s-1}{2}\rfloor +1$ for all vertices $x_{1}\in X_{1}$ and $x_{2}\in X_{2}$ with $x_{1}x_{2}\notin E(G^{r})$. Since $N \ge \lfloor \frac{s-1}{2}\rfloor + 1$, applying Theorem 1 with $n= N$ and $m = \lfloor \frac{s-1}{2}\rfloor + 1$, we obtain a path P in $G^{r}$ with

$$\begin{aligned} |V(P)|\ge 2\left( \left\lfloor \frac{s-1}{2}\right\rfloor +1\right) \ge 2\left( \frac{s-2}{2}+1\right) =s, \end{aligned}$$

as desired. $\square$

Lemma 5

Lets be an odd integer with$s\ge 3$, and let$t_{1}$ and$t_{2}$ be non-negative integers such that$t_{1}>t_{2}$ and$t_{1}\not \equiv 0~(\text{ mod } \frac{s-1}{2})$. Then$b(P_{s},B_{t_{1},t_{2}})\le \frac{s-1}{2}+t_{1}$.

Proof

Let $N=\frac{s-1}{2}+t_{1}$. Let $X_{1}$ and $X_{2}$ be the partite sets of $K_{N,N}$. Let $G^{r}$ and $G^{b}$ be edge-disjoint spanning subgraphs of $K_{N,N}$ with $E(G^{r})\cup E(G^{b})=E(K_{N,N})$. By way of contradiction, suppose that $P_{s}\not \subset G^{r}$ and $B_{t_{1},t_{2}}\not \subset G^{b}$. Since $t_{1}>t_{2}$, it follows from Lemma 3 that $\max \{d_{G^{r}}(x_{1}),d_{G^{r}}(x_{2})\}\ge N-t_{1}=\frac{s-1}{2}$ for all vertices $x_{1}\in X_{1}$ and $x_{2}\in X_{2}$ with $x_{1}x_{2}\notin E(G^{r})$.

Claim 1

If a componentH of$G^{r}$ contains a path of order$s-1$, then $|V(H)|=s-1$.

Proof

Suppose that H contains a path $P=y_{1}y_{2}\cdots y_{s-1}$. Without loss of generality, we may assume that $y_{1}\in X_{1}$. Note that $y_{s-1}\in X_{2}$. Since H contains no path of order s, $N_{H}(y_{1})\subseteq V(P)\cap X_{2}$ and $N_{H}(y_{s-1})\subseteq V(P)\cap X_{1}$. If $y_{1}y_{s-1}\notin E(H)$, then $d_{H}(y_{1})\le |V(P)\cap (X_{2}-\{y_{s-1}\})|=\frac{s-3}{2}$, $d_{H}(y_{s-1})\le |V(P)\cap (X_{1}-\{y_{1}\})|=\frac{s-3}{2}$, which contradicts the fact that $\max \{d_{H}(y_{1}),d_{H}(y_{s-1})\}\ge \frac{s-1}{2}$. Thus $y_{1}y_{s-1}\in E(H)$. In particular, $y_{1}y_{2}\cdots y_{s-1}y_{1}$ is a cycle of H. Since $G^{r}$ contains no path of order s, it follows that $N_{H}(y_{i})\subseteq V(P)$ for all $i~(1\le i\le s-1)$. In particular, $H[V(P)]=H$. $\square$

Since $N = \frac{s-1}{2}+ t_1 \ge \frac{s-1}{2}$, applying Theorem 1 with $n= N$ and $m = \frac{s-1}{2}$, we obtain a path P in $G^{r}$ with $|V(P)|\ge 2\cdot \frac{s-1}{2}= s-1$. It follows from Claim 1 that $G^{r}[V(P)]$ is a component of $G^{r}$. In particular, $d_{G^{r}[V(P)]}(x)\le \frac{s-1}{2}=N-t_{1}<N-t_{2}$ for all $x\in V(P)$. This together with Lemma 3 implies that $d_{G^{r}}(u)\ge N-t_{1}$ for all $u\in V(G^{r})-V(P)$.

Since $N-\frac{s-1}{2}=t_{1}\ge 1$, $V(G^{r})-V(P)\ne \emptyset$. Let H be a component of $G^{r}$ other than $G^{r}[V(P)]$. Since $d_{G^{r}}(u)\ge N-t_{1}=\frac{s-1}{2}$ for every $u\in V(H)$, it follows from Lemma 1 that H contains a path of order $s-1$. Then by Claim 1, $|V(H)|=s-1$ (i.e., $|V(H)\cap X_{1}|=\frac{s-1}{2}$). Since H is arbitrary, $N~(=|X_{1}|)$ is a multiple of $\frac{s-1}{2}$, which contradicts the assumption that $t_{1}\not \equiv 0~(\text{ mod } \frac{s-1}{2})$. $\square$

Lemma 6

Lets be an integer with$s\ge 2$, and let$t_{1}$ and$t_{2}$ be non-negative integers with$\lfloor \frac{s-1}{2} \rfloor>t_{1}>t_{2}$. Then

$$\begin{aligned} b(P_{s},B_{t_{1},t_{2}})\le {\left\{ \begin{array}{ll} 2t_{1}+1 &{} \left(2t_{1}-t_{2}\ge \lfloor \frac{s-1}{2} \rfloor \right )\\ \lfloor \frac{s-1}{2}\rfloor +t_{2}+1 &{} (\text{ otherwise }). \end{array}\right. } \end{aligned}$$

In other words, Lemma 6 concludes that $b(P_{s},B_{t_{1},t_{2}}) \le \lfloor \frac{s - 1}{2} \rfloor + t_{2} + 1 + \max \{2t_{1}-t_{2}-\lfloor \frac{s-1}{2} \rfloor ,0\}$.

Proof of Lemma 6

Let $N=\lfloor \frac{s-1}{2}\rfloor +t_{2}+1+\max \{2t_{1}-t_{2}-\lfloor \frac{s-1}{2} \rfloor ,0\}$. Let $X_{1}$ and $X_{2}$ be the partite sets of $K_{N,N}$. Let $G^{r}$ and $G^{b}$ be edge-disjoint spanning subgraphs of $K_{N,N}$ with $E(G^{r})\cup E(G^{b})=E(K_{N,N})$. Suppose that $B_{t_{1},t_{2}}\not \subset G^{b}$ as a subgraph. It suffices to show that $P_{s}\subset G^{r}$. Note that $N-t_{2}\ge (\lfloor \frac{s-1}{2}\rfloor +t_{2}+1)-t_{2}=\lfloor \frac{s-1}{2}\rfloor +1$ and $N-t_{1}\ge \frac{N+1}{2}$ because

$$\begin{aligned} 2(N-t_{1})-(N+1)&= N-2t_{1}-1\\&= \left\lfloor \frac{s-1}{2} \right\rfloor +t_{2}+\max \left\{ 2t_{1}-t_{2}-\left\lfloor \frac{s-1}{2} \right\rfloor ,0\right\} -2t_{1}\\&= {\left\{ \begin{array}{ll} 0 &{} \left(2t_{1}-t_{2}\ge \lfloor \frac{s-1}{2} \rfloor \right)\\ \lfloor \frac{s-1}{2}\rfloor -(2t_{1}-t_{2})>0 &{} (\text{ otherwise }). \end{array}\right. } \end{aligned}$$

This together with Lemma 3 implies that, for all vertices $x_{1}\in X_{1}$ and $x_{2}\in X_{2}$ with $x_{1}x_{2}\notin E(G^{r})$,

• $\max \{d_{G^{r}}(x_{1}),d_{G^{r}}(x_{2})\}\ge N-t_{2}\ge \lfloor \frac{s-1}{2}\rfloor +1$ or

• $\min \{d_{G^{r}}(x_{1}),d_{G^{r}}(x_{2})\}\ge N-t_{1}\ge \frac{N+1}{2}$.

Since $N =\lfloor \frac{s-1}{2}\rfloor +t_{2}+1+\max \{2t_{1}-t_{2}-\lfloor \frac{s-1}{2} \rfloor ,0\}\ge \lfloor \frac{s-1}{2}\rfloor + 1$, applying Theorem 1 with $n= N$ and $m = \lfloor \frac{s-1}{2}\rfloor + 1$, we obtain a path P in $G^{r}$ with

$$\begin{aligned} |V(P)|\ge 2\left( \left\lfloor \frac{s-1}{2}\right\rfloor +1\right) \ge 2\left( \frac{s-2}{2}+1\right) =s, \end{aligned}$$

as desired. $\square$

Proof of Theorem 2

Let s, $t_{1}$ and $t_{2}$ be as in Theorem 2. We first prove the theorem for the case where $s=2$, i.e., $b(P_{2},B_{t_{1},t_{2}})=t_{1}+1$. By Lemma 4, we have $b(P_{2},B_{t_{1},t_{2}})\le t_{1}+1$. Now we prove that $b(P_{2},B_{t_{1},t_{2}})\ge t_{1}+1$. Let $X_{1}$ and $X_{2}$ be the partite sets of $K_{t_{1},t_{1}}$. Let $G^{r}$ be the graph obtained from $K_{t_{1},t_{1}}$ by deleting all edges, and let $G^{b}=K_{t_{1},t_{1}}$. Then it is clear that $P_{2}\not \subset G^{r}$ and $B_{t_{1},t_{2}}\not \subset G^{b}$, and so $b(P_{2},B_{t_{1},t_{2}})\ge t_{1}+1$. Thus we may assume that $s\ge 3$. Let $q\in {\mathbb {N}}\cup \{0\}$ and $r~(0\le r\le \lfloor \frac{s-1}{2}\rfloor -1)$ be the integers satisfying $t_{1}=\left\lfloor \frac{s-1}{2}\right\rfloor q+r$.

• (i) Suppose that $t_{1}=t_{2}$. Let $N=\lfloor \frac{s-1}{2}\rfloor +t_{1}+1$. By Lemma 4, we have $b(P_{s},B_{t_{1},t_{2}})\le N$. Now we prove that $b(P_{s},B_{t_{1},t_{2}})\ge N$. Let $X_{1}$ and $X_{2}$ be the partite sets of $K_{N-1,N-1}$. We partition $X_{i}$ into $q+2$ sets $X^{0}_{i},X^{1}_{i},\ldots ,X^{q+1}_{i}$ with $|X^{0}_{i}|=|X^{1}_{i}|=\cdots =|X^{q}_{i}|=\lfloor \frac{s-1}{2}\rfloor$ and $|X^{q+1}_{i}|=r$. Note that $X^{q+1}_{i}=\emptyset$ if and only if $t_{1}\equiv 0~(\text{ mod } \lfloor \frac{s-1}{2}\rfloor )$. Let $G^{r}$ be the spanning subgraph of $K_{N-1,N-1}$ such that

  $$\begin{aligned} E(G^{r})=\bigcup _{0\le j\le q+1}\{x_{1}x_{2}:x_{1}\in X^{j}_{1},~x_{2}\in X^{j}_{2}\}, \end{aligned}$$

  and let $G^{b}=K_{N-1,N-1}-E(G^{r})$. Then the order of longest paths of $G^{r}$ is at most $2\lfloor \frac{s-1}{2} \rfloor ~(\le s-1)$. Furthermore, since $\min \{d_{G^{b}}(x_{1}),d_{G^{b}}(x_{2})\}\le (N-1)-\lfloor \frac{s-1}{2} \rfloor =t_{1}~(=t_{2})$ for every edge $x_{1}x_{2}\in E(G^{b})$, we see that $B_{t_{1},t_{2}}\not \subset G^{b}$. Therefore $b(P_{s},B_{t_{1},t_{2}})\ge N$.

• (ii-a) Suppose that $t_{1}>t_{2}$ and $t_{1}\ge \lfloor \frac{s-1}{2}\rfloor$. Note that $q\ge 1$. Let

  $$\begin{aligned} N= {\left\{ \begin{array}{ll} \lfloor \frac{s-1}{2}\rfloor +t_{1}+1 &{} \left(s \text{ is } \text{ even, } \text{ or } s \text{ is } \text{ odd } \text{ and } t_{1}\equiv 0~\left(\text{ mod } \frac{s-1}{2}\right)\right)\\ \lfloor \frac{s-1}{2}\rfloor +t_{1} &{} (\text{ otherwise }). \end{array}\right. } \end{aligned}$$

  By Lemmas 4 and 5, we have $b(P_{s},B_{t_{1},t_{2}})\le N$. Now we prove that $b(P_{s},B_{t_{1},t_{2}})\ge N$. Let $X_{1}$ and $X_{2}$ be the partite sets of $K_{N-1,N-1}$. If s is even, or s is odd and $t_{1}\equiv 0~(\text{ mod } \frac{s-1}{2})$, we partition $X_{i}$ into $q+2$ sets $X^{0}_{i},X^{1}_{i},\ldots ,X^{q+1}_{i}$ with $|X^{0}_{i}|=|X^{1}_{i}|=\cdots =|X^{q}_{i}|=\lfloor \frac{s-1}{2}\rfloor$ and $|X^{q+1}_{i}|=r$; otherwise, we partition $X_{i}$ into $q+2$ sets $X^{0}_{i},X^{1}_{i},\ldots ,X^{q+1}_{i}$ with

  • $|X^{j}_{i}|=\frac{s-1}{2}$ for $i\in \{1,2\}$ and $j~(0\le j\le q)$ with $(i,j)\notin \{(1,0),(2,1)\}$,

  • $|X^{0}_{1}|=|X^{1}_{2}|=\frac{s-3}{2}$ and

  • $|X^{q+1}_{1}|=|X^{q+1}_{2}|=r$.

  Note that $X^{q+1}_{i}=\emptyset$ if and only if $t_{1}\equiv 0~(\text{ mod } \lfloor \frac{s-1}{2}\rfloor )$. Let $G^{r}$ be the spanning subgraph of $K_{N-1,N-1}$ obtained by

  • joining all vertices in $X^{0}_{1}$ to all vertices in $X^{0}_{2}\cup X^{q+1}_{2}$,

  • joining all vertices in $X^{1}_{2}$ to all vertices in $X^{1}_{1}\cup X^{q+1}_{1}$ and

  • for each $j~(2\le j\le q)$, joining all vertices in $X^{j}_{1}$ to all vertices in $X^{j}_{2}$,

  and let $G^{b}=K_{N-1,N-1}-E(G^{r})$. If s is even, then the order of longest paths of $G^{r}$ is at most $2\lfloor \frac{s-1}{2} \rfloor +1=2\cdot \frac{s-2}{2}+1=s-1$; if s is odd and $t_{1}\equiv 0~(\text{ mod } \frac{s-1}{2})$, then the order of longest paths of $G^{r}$ is $2\lfloor \frac{s-1}{2} \rfloor =2\cdot \frac{s-1}{2}=s-1$; if s is odd and $t_{1}\not \equiv 0~(\text{ mod } \frac{s-1}{2})$, then the order of longest paths of $G^{r}$ is at most

  $$\begin{aligned} \max \left\{ 2\cdot \frac{s-1}{2} ,2\cdot \frac{s-3}{2} +1\right\} =s-1. \end{aligned}$$

  Furthermore, since we easily check that $d_{G^{b}}(x)\le t_{1}$ for all $x\in V(G^{b})$, $B_{t_{1},t_{2}}\not \subset G^{b}$. Therefore $b(P_{s},B_{t_{1},t_{2}})\ge N$.

• (ii-b) Suppose that $t_{1}>t_{2}$ and $t_{1}<\lfloor \frac{s-1}{2}\rfloor$. Let $N=\lfloor \frac{s-1}{2}\rfloor +t_{2}+1+\max \{2t_{1}-t_{2}-\lfloor \frac{s-1}{2} \rfloor ,0\}$. By Lemma 6, we have $b(P_{s},B_{t_{1},t_{2}})\le N$. Now we prove that $b(P_{s},B_{t_{1},t_{2}})\ge N$. Let $X_{1}$ and $X_{2}$ be the partite sets of $K_{N-1,N-1}$. If $2t_{1}-t_{2}\ge \lfloor \frac{s-1}{2} \rfloor$ (i.e., $N-1=2t_{1}$), we partition $X_{i}$ into two sets $X^{1}_{i}$ and $X^{2}_{i}$ with $|X^{1}_{i}|=|X^{2}_{i}|=t_{1}$; otherwise (i.e., $N=\lfloor \frac{s-1}{2}\rfloor +t_{2}$), we partition $X_{i}$ into two sets $X^{1}_{i}$ and $X^{2}_{i}$ with $|X^{1}_{i}|=\lfloor \frac{s-1}{2} \rfloor$ and $|X^{2}_{i}|=t_{2}$. Let $G^{r}$ be the spanning subgraph of $K_{N-1,N-1}$ such that

  $$\begin{aligned} E(G^{r})=\bigcup _{j\in \{1,2\}}\{x_{1}x_{2}:x_{1}\in X^{j}_{1},~x_{2}\in X^{j}_{2}\}, \end{aligned}$$

  and let $G^{b}=K_{N-1,N-1}-E(G^{r})$. Since $t_{2}<t_{1}<\lfloor \frac{s-1}{2} \rfloor$, the order of longest paths of $G^{r}$ is at most $2\lfloor \frac{s-1}{2} \rfloor ~(\le 2\cdot \frac{s-1}{2}=s-1)$. Furthermore, if $2t_{1}-t_{2}\ge \lfloor \frac{s-1}{2} \rfloor$, then $d_{G^{b}}(x)=(N-1)-t_{1}=t_{1}$ for all $x\in V(G^{b})$; if $2t_{1}-t_{2}<\lfloor \frac{s-1}{2} \rfloor$, then $\min \{d_{G^{b}}(x_{1}),d_{G^{b}}(x_{2})\}=t_{2}$ for every edge $x_{1}x_{2}\in E(G^{b})$. In either case, $B_{t_{1},t_{2}}\not \subset G^{b}$. Therefore $b(P_{s},B_{t_{1},t_{2}})\ge N$.

This completes the proof of Theorem 2. $\square$