A New Proof on the Bipartite Turán Number of Bipartite Graphs

Shiqian Wang

School of Mathematics and Statistics, Shandong Normal University, Jinan, China.

DOI: 10.4236/eng.2024.169022                

Abstract

The bipartite Turán number of a graph H, denoted by $\text{ex}\left(m,n;H\right)$ , is the maximum number of edges in any bipartite graph $G=\left(A,B;E\left(G\right)\right)$ with $\left|A\right|=m$ and $\left|B\right|=n$ which does not contain H as a subgraph. When$\min \left\{m,n\right\}>2t$ , the problem of determining the value of $\text{ex}\left(m,n;K_{m-t,n-t}\right)$ has been solved by Balbuena et al. in 2007, whose proof focuses on the structural analysis of bipartite graphs. In this paper, we provide a new proof on the value of $\text{ex}\left(m,n;K_{m-t,n-t}\right)$ by virtue of algebra method with the tool of adjacency matrices of bipartite graphs, which is inspired by the method using $\left\{0,1\right\}$ -matrices due to Zarankiewicz [Problem P 101. Colloquium Mathematicum, 2(1951), 301].

Keywords

Bipartite Turán Number, Adjacency Matrix, Zarankiewicz Problem

1. Introduction

In this paper, the graphs are all undirected simple graphs. Let G and H be two graphs. We say that a graph G is H-free if G does not contain a subgraph isomorphic to H. In 1941, Turán proved that the extremal graph which does not contain $K_{r+1}$ as a subgraph is the Turán graph $T_r\left(n\right)$ , where Turán graph $T_r\left(n\right)$ is the

complete r-partite graph on n vertices with each part containing $\lceil \frac{n}{r}\rceil$ or $\lfloor \frac{n}{r}\rfloor$

vertices. Turán’s theorem [1] is a fundamental theorem in graph theory, which is the beginning of extremal graph theory. For a simple graph H, the Turán number of H, denoted by $\text{ex}\left(n,H\right)$ , is the maximum number of edges among H-free graphs with n vertices, i.e.,

$\text{ex}\left(n,H\right)=\text{max}\left\{e\left(G\right):\left|G\right|=n,H\cancel{\subset }G\right\}$ .

Turán’s theorem states that $\text{ex}\left(n,K_{r+1}\right)\le \left(1-\frac{1}{r}\right)\frac{n^2}{2}$ . Erdős, Stone and Simonovits [2] [3] generalized this result by using the chromatic number of graph.

The Erdős-Stone-Simonovits theorem states that, for any given graph H and any fixed $ϵ>0$ , there exists a positive integer $n_0$ such that, for any $n\ge n_0$ ,

$\left(1-\frac{1}{\chi \left(H\right)-1}-ϵ\right)\frac{n^2}{2}\le \text{ex}\left(n,H\right)\le \left(1-\frac{1}{\chi \left(H\right)-1}+ϵ\right)\frac{n^2}{2}$ ,

where $\chi \left(H\right)$ is the chromatic number of H. The theorem means that it is asymptotically best possible for any graph H with $\chi \left(H\right)\ge 3$ .

When the forbidden subgraph H is a bipartite graph, there are lots of interesting results. In 1954, Kővári, Sós and Turán [4] showed that, for $r\le t$ ,

$\text{ex}\left(n,K_{r,t}\right)=O\left(n^{2-\frac{1}{r}}\right)$ . Call a graph H r-degenerate if each subgraph of H has a vertex of degree at most r. Note that $K_{r,t}$ is an r-degenerate bipartite graph and$\text{ex}\left(n,K_{r,t}\right)=O\left(n^{2-\frac{1}{r}}\right)$ . Motivated by the Kővári-Sós-Turán theorem, the following conjecture was proposed by Erdős in 1966.

Conjecture 1. [5] If H is an r-degenerate bipartite graph, then $\text{ex}\left(n,H\right)=O\left(n^{2-\frac{1}{r}}\right)$ .

This conjecture is widely open. Alon, Rónyai and Szabó [6], Kollár, Rónyai and Szabó [7], respectively, showed that the upper bound of this conjecture is in fact sharp for r-degenerate bipartite graph. They proved that there exists a positive

constant $c_r$ depending on r such that $\text{ex}\left(n,K_{r,t}\right)\ge c_r{n}^{2-\frac{1}{r}}$ for $r\ge 2$ and $t>\left(r-1\right)!$ . The following result due to Füredi [8] confirmed the conjecture in

part in 1991. Later, Alon, Krivelevich and Sudakov [9] gave a new proof for this result in 2003.

Theorem 2. [8] [9] If H is a bipartite graph with maximum degree at most r on one part, then there exists a constant c depending only on H such that

$\text{ex}\left(n,H\right)\le c\cdot n^{2-\frac{1}{r}}$ .

In [9], Alon, Krivelevich and Sudakov showed a weaker bound for Conjecture 1.

Theorem 3. [9] If H is an r-degenerate bipartite graph, then

$\text{ex}\left(n,H\right)=O\left(n^{2-\frac{1}{4r}}\right)$ .

As a generalization of the Turán number, the bipartite Turán number, denoted by $\text{ex}\left(m,n;H\right)$ , is the maximum number of edges among H-free bipartite graphs with two parts of sizes m and n for a given bipartite graph H. Denote by $\text{EX}\left(m,n;H\right)$ the set of extremal bipartite H-free graphs on n vertices with $\text{ex}\left(m,n;H\right)$ edges. The problem of determining the value of $\text{ex}\left(m,n;H\right)$ for any given graph H is called the bipartite Turán problem, which is closely related to the Turán problem. Denote a path on l vertices by $P_l$ . Gyárfás, Rousseau and Schelp [10] considered the bipartite Turán number of paths.

Theorem 4. [10] Let $n\ge m$ . Then

$\text{ex}\left(n,m;P_{2l}\right)=\{\begin{array}{ll}mn,\hfill & m\le l-1;\hfill \\ \left(l-1\right)n,\hfill & l-1<m<2\left(l-1\right);\hfill \\ \left(l-1\right)\left(n+m-2l+2\right),\hfill & m\ge 2\left(l-1\right).\hfill \end{array}$ (1)

Let $M_k$ be a matching of k edges. The below result, due to Li, Tu and Jin [11], shows us $\text{ex}\left(n,m;M_k\right)$ for $n\ge m\ge k$ and the corresponding extremal graph.

Theorem 5. [11] Let $n\ge m\ge k$ . Then

$\text{ex}\left(n,m;M_k\right)=\left(k-1\right)n$ .

Moreover, the unique extremal graph is $K_{k-1,n}\cup K_{m-k+1,0}$ .

For two positive integers m, n and a given graph H, let $s\left(m,n;H\right)$ denote the smallest positive integer s such that if G is a bipartite graph with two parts A, B, where $\left|A\right|=m$ , $\left|B\right|=n$ , and G has at least s edges, then G must contain H as a subgraph. Clearly,$s\left(m,n;H\right)=\text{ex}\left(m,n;H\right)+1$ . A cycle consisted of l vertices is denoted as $C_l$ . Kővári, Sós and Turán [4] obtained the classical result that

$\text{ex}\left(n,n;C_4\right)=\left(1+o\left(1\right)\right)n^{\frac{3}{2}}$ . For a constant c, Erdős, Sárközy and Sós [12] conjectured in 1995 that

$\text{ex}\left(m,n;C_6\right)+1=s\left(m,n;C_6\right)<c{\left(mn\right)}^{\frac{2}{3}}$ (2)

when $m\le n\le m^2$ and

$\text{ex}\left(m,n;C_6\right)+1=s\left(m,n;C_6\right)<2n+c{\left(mn\right)}^{\frac{2}{3}}$ (3)

when $n>m^2$ .

(2) was confirmed by Sárközy [13]. (3) was first studied by Sárközy [13] and it was settled by Győri [14]. Motivated by the result on the bipartite Turán number of short cycle, Győri [14] proposed a more general conjecture of long cycles.

Conjecture 6. [14] $\text{ex}\left(m,n;C_{2t}\right)+1=s\left(m,n;C_{2t}\right)\le \left(t-1\right)n+m-t+2$ , where $n\ge m^2$ , $m\ge t\ge 3$ .¹

Győri [15] himself disproved Conjecture 6 for $t=3$ . Balbuena et al. [16] further disproved it when $t\le \frac{m+1}{2}$ . In 2021, Li and Ning [17] showed that $\text{ex}\left(m,n;C_{2t}\right)=\left(t-1\right)n+m-t+1$ for$n\ge m\ge t\ge \frac{m}{2}+1$ , which improved a result of Jackson in [18].

When the forbidden subgraph H is a complete bipartite graph, the problem of determining the value $\text{ex}\left(m,n;H\right)$ is closely related to the Zarankiewicz problem. In 1951, Zarankiewicz [19] proposed the following question: Determine the smallest positive integer $\tilde{z}\left(m,n;s,t\right)$ such that each $\left\{0,1\right\}$ -matrix with m rows and n columns containing $\tilde{z}\left(m,n;s,t\right)$ 1’s has a submatrix with s rows and t columns consisting entirely of 1’s. Combined with the adjacency matrix of bipartite graph, this extremal problem may be formulated in graph-theoretic terms. It is equivalent to find the least positive integer $\tilde{z}\left(m,n;s,t\right)$ such that each bipartite graph on m black vertices and n white vertices with $\tilde{z}\left(m,n;s,t\right)$ edges has a complete bipartite subgraph on s black vertices and t white vertices. In [20]-[22], use $z\left(m,n;s,t\right)$ to represent the maximum number of edges among bipartite graphs $G=\left(A,B;E\left(G\right)\right)$ with $\left|A\right|=m$ and $\left|B\right|=n$ such that they do not contain any complete bipartite graph with s vertices in A and t vertices in B. The corresponding extremal family of bipartite graphs is denoted by $Z\left(m,n;s,t\right)$ . Obviously, $\tilde{z}\left(m,n;s,t\right)=z\left(m,n;s,t\right)+1$ and $\text{ex}\left(m,n,K_{s,t}\right)\le z\left(m,n;s,t\right)$ , $\text{ex}\left(m,n;K_{s,t}\right)\le z\left(m,n;t,s\right)$ . Note that, when $2\le s<m$ , $2\le t<n$ and $m<t$ or $n<s$ , $\text{ex}\left(m,n;K_{s,t}\right)=\text{ex}\left(m,n;K_{t,s}\right)$ ; however, there is $z\left(m,n;s,t\right)<z\left(m,n;t,s\right)=mn$ .

Goddard, Henning and Oellermann [20] obtained the exact values of $z\left(n,n;2,2\right)$ for $n\le 20$ and showed that in some cases the family $Z\left(n,n;2,2\right)$ contains only

one extremal graph. Kővári, Sós and Turán [4] proved that $z\left(n,n;2,2\right)\le 2n+n^{\frac{3}{2}}$ .

Further, if q is a prime, then $z\left(q^2+q,q^2;2,2\right)=q^3+q^2$ . Griggs and Ouyang [21] studied the so-called “half–half” case, i.e., the function $z\left(2s,2t;s,t\right)$ .

Theorem 7. [21] Let $s\le t$ . Then

$4st-\left(2t+2s-\gcd \left(s,t\right)+1\right)\le z\left(2s,2t;s,t\right)\le 4st-\left(2t+s+1\right)$ ,

where $\gcd \left(s,t\right)$ is the greatest common divisor of s and t.

In 2007, Balbuena et al. [22] determined the exact value of $z\left(m,n;s,t\right)$ and characterized the family $Z\left(m,n;s,t\right)$ of extremal graphs if $\max \left\{m,n\right\}<s+t$ . They gave the following results.

Theorem 8. [22] Let $m,n,s,t$ be four integers with $2\le s<m$ , $2\le t<n$ and such that $\max \left\{m,n\right\}<s+t$ . Then

$\{\begin{array}{l}z\left(m,n;s,t\right)=\text{ex}\left(m,n;K_{s,t}\right)=mn-\left(m+n-s-t+1\right),\hfill \\ Z\left(m,n;s,t\right)=\text{EX}\left(m,n;K_{s,t}\right)=\left\{K_{m,n}-M\right\},\hfill \end{array}$ (4)

where M is any matching with cardinality $m+n-s-t+1$ .

In this article, we prove the following result by virtue of algebra method. Our proof is different from the one of Theorem 8, but it is inspired by the method using $\left\{0,1\right\}$ -matrices due to Zarankiewicz in [19].

Theorem 9. Let $m,n,t$ be three positive integers with $\min \left\{m,n\right\}>2t$ . Then $\text{ex}\left(m,n;K_{m-t,n-t}\right)=mn-2t-1$ .

The rest of this paper is organized as follows. In Section 2, we first introduce some notations and definitions. By virtue of adjacency matrix, the proof of Theorem 9 is given. In Section 3, we give some concluding remarks.

2. Preliminaries and Proofs

Before giving the proof, we introduce some notations and definitions. In this paper, a graph $G=\left(A,B;E\left(G\right)\right)$ is denoted as a bipartite graph, where $V\left(G\right)=A\cup B$ , $A\cap B=\varnothing$ and every edge in $E\left(G\right)$ has one endpoint in A and the other in B. Call $G=\left(A,B;E\left(G\right)\right)$ a complete bipartite graph if every vertex in A is adjacent to all vertices in B and usually denote it by $K_{m,n}$ when $\left|A\right|=m$ and $\left|B\right|=n$ . A bipartite graph $G=\left(A,B;E\left(G\right)\right)$ is balanced if $\left|A\right|=\left|B\right|$ . A matching of graph H is a subset of $E\left(H\right)$ in which no two edges share a same vertex. We say that vertex v is a saturated vertex of M if v is incident with an edge in the matching M. Otherwise, the vertex v is an exposed vertex of M. A matching of H is maximum if there is no matching with greater cardinality in H.

Next, we introduce the adjacency matrix of a bipartite graph that describes structural properties of graphs. Let $F=\left(A,B;E\left(F\right)\right)$ be a bipartite graph with two parts $A=\left\{u_1,u_2,\cdots ,u_m\right\}$ and $B=\left\{v_1,v_2,\cdots ,v_n\right\}$ . The adjacency matrix of F is an $m\times n$ matrix M with 1 or 0 in the position of $\left(u_i,v_j\right)$ corresponding to $u_i$ and $v_j$ are adjacent or not, respectively, for $1\le i\le m$ and $1\le j\le n$ . When we delete t edges of a bipartite graph, its adjacency matrix will have t corresponding elements changed from 1 to 0.

For example, let $F=\left(A,B;E\left(F\right)\right)$ be a bipartite graph as shown in Figure 1 with $A=\left\{u_1,u_2,u_3,u_4\right\}$ , $B=\left\{v_1,v_2,v_3,v_4,v_5\right\}$ and $E\left(F\right)=\left\{u_1{v}_1,u_1{v}_2,u_2{v}_2,u_2{v}_3,u_3{v}_3,u_3{v}_4,u_4{v}_4,u_4{v}_5\right\}$ .

Figure 1. Bipartite graph F.

Denote the adjacency matrix of bipartite graph F by M. Then we have

$M=\left[\begin{array}{ccccc}1& 1& 0& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 0\\ 0& 0& 0& 1& 1\end{array}\right].$ (5)

After deleting the edges $u_1{v}_1,u_2{v}_3$ and $u_4{v}_5$ of graph F, the corresponding adjacency matrix $M^{\prime }$ is as below.

$M^{\prime }=\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 1& 0\\ 0& 0& 0& 1& 0\end{array}\right].$ (6)

Next, we give the proof of our result by virtue of adjacency matrices of bipartite graphs and graph structural analysis.

Proof of Theorem 9.

Proof. Let $m,n,t$ be three positive integers with $n\ge m>2t$ . Assume that complete bipartite graph $K_{m,n}=\left(A,B;E\left(K_{m,n}\right)\right)$ and $\left|A\right|=m$ , $\left|B\right|=n$ .

Firstly, we prove that $\text{ex}\left(m,n;K_{m-t,n-t}\right)\ge mn-2t-1$ . Consider graph $G_1=\left(A_1,B_1;E\left(G_1\right)\right)$ which is obtained by deleting a matching $M_1$ of cardinality $2t+1$ from the complete bipartite graph $\left(A,B;E\left(K_{m,n}\right)\right)$ . We prove that $G_1$ does not contain $K_{m-t,n-t}$ as a subgraph. Otherwise, we may assume that $G_1$ contains a $K_{m-t,n-t}$ which has two parts $A^{\prime }\subseteq A$ and $B^{\prime }\subseteq B$ and $\left|A^{\prime }\right|=m-t$ ,$\left|B^{\prime }\right|=n-t$ . Then $A^{\prime }$ contains at least $t+1$ saturated vertices of $M_1$ . Noting that the number of vertices in $B\backslash B^{\prime }$ is t, at least one saturated vertex in $A^{\prime }$ is adjacent to some saturated vertex of $B^{\prime }$ , which implies that at least one edge in $K_{m-t,n-t}$ belongs to $M_1$ . It is a contradiction. So $G_1$ , with $mn-2t-1$ edges, does not contain $K_{m-t,n-t}$ as a subgraph. Therefore, $\text{ex}\left(m,n;K_{m-t,n-t}\right)\ge mn-2t-1$ .

Next, we prove that $\text{ex}\left(m,n;K_{m-t,n-t}\right)\le mn-2t-1$ . That is to say, it needs to be proved that after arbitrarily deleted 2t edges of $K_{m,n}$ , the resulting graph contains $K_{m-t,n-t}$ as a subgraph. We use the adjacency matrix of the bipartite graph to prove this. After 2t edges are deleted from $K_{m,n}$ , there are 2t elements in the adjacency matrix of $K_{m,n}$ changed from 1 to 0. Denote this adjacency matrix by C. We need to prove that C has a sub-matrix $C^{\prime }$ with $m-t$ rows and $n-t$ columns whose elements are all 1’s. We rearrange the rows of matrix C in the order of increasing numbers of 0’s and label them row (1), row (2), $\cdots$ , row (m). Denote such a matrix by $\widehat{C}$ . Obviously, for $1\le j\le m-2t$ , the number of 0’s in row (j) is 0. Besides, we have the following claim.

Claim 1. For $1\le i\le t$ , the number of 0’s in the row $\left(m-2t+i\right)$ is at most 1 in $\widehat{C}$ .

Proof. If the number of 0’s in the row $\left(m-t\right)$ is at least 2, then the number of 0’s in each row $\left(m-t+k\right)$ is at least 2, where $1\le k\le t$ . Hence, the number of 0’s in matrix $\widehat{C}$ is at least $2t+2$ , contradicting that matrix $\widehat{C}$ has 2t 0’s. Therefore, the number of 0’s in the row $\left(m-t\right)$ is at most 1. It follows that the number of 0’s in row $\left(m-2t+i\right)$ is also at most 1, where $1\le i\le t-1$ . The proof is completed.

Therefore, the number of 0’s in the first $m-t$ rows is at most t. For the first $m-t$ rows, we delete the columns of $\widehat{C}$ which include element 0. Then there are at least $n-t$ columns whose elements are all 1’s. We label these $n-t$ columns as column (1), column (2), $\cdots$ , column $\left(n-t\right)$ . Now the intersection of row (1), row (2), $\cdots$ , row $\left(m-t\right)$ and column (1), column (2), $\cdots$ , column $\left(n-t\right)$ forms a sub-matrix $C^{\prime }$ whose elements are all 1’s. Hence, after arbitrarily deleted 2t edges of $K_{m,n}$ , the resulting graph contains $K_{m-t,n-t}$ as a subgraph. So $\text{ex}\left(m,n;K_{m-t,n-t}\right)\le mn-2t-1$ .

Therefore, we have $\text{ex}\left(m,n;K_{m-t,n-t}\right)=mn-2t-1$ . The proof is completed.

3. Concluding Remarks

As it well known, for positive integers m, n and t with $\min \left\{m,n\right\}>2t$ , the value of $\text{ex}\left(m,n;K_{m-t,n-t}\right)$ has been solved by Balbuena et al. [22] in 2007, whose proof focuses more on the structural analysis of bipartite graphs. However, in this article, we provide a new perspective to prove the value of $\text{ex}\left(m,n;K_{m-t,n-t}\right)$ . By the virtue of algebra method, we use the tool of adjacency matrices of bipartite graphs to prove this result. By Theorem 9, the result of the Turán number of the balanced bipartite graphs may be drawn naturally.

Corollary 10. Let $n,t$ be two positive integers with $2t<n$ . Then $\text{ex}\left(n,n;K_{n-t,n-t}\right)=n^2-2t-1$ .

When $2t=n$ , Balbuena et al. [22] proved that $\text{ex}\left(n,n;K_{n-t,n-t}\right)=n^2-3t-1$ . And for $2t>n$ , the value of $\text{ex}\left(n,n;K_{n-t,n-t}\right)$ has only been resolved in a few cases. There are still a lot of works that can be studied for the bipartite Turán number problem of bipartite graphs. Other tools may be explored to solve the related questions. For instance, laplacian spectral radius of bipartite graphs [23] may be used to solve bipartite Turán number problem of bipartite graphs. And in [24], the methods of finding rainbow matching in bipartite graphs are also worth learning to solve the related extreme value problem.

NOTES

¹The original conjectured value $\left(t-1\right)n+m-t+1$ in [14] may be a misprint (see the remark on page 748 in [16]).

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Turán, P. (1941) On an Extremal Problem in Graph Theory. Matematikai eś Fizikai Lapok, 48, 436-452.
[2]	Erdős, P. and Simonovits, M. (1966) A Limit Theorem in Graph Theory. Studia Scientiarum Mathematicarum Hungarica, 1, 51-57.
[3]	Erdős, P. and Stone, A.H. (1946) On the Structure of Linear Graphs. Bulletin of the American Mathematical Society, 52, 1087-1091.
[4]	Kóvari, T., Sós, V. and Turán, P. (1954) On a Problem of K. Zarankiewicz. Colloquium Mathematicum, 3, 50-57. https://doi.org/10.4064/cm-3-1-50-57
[5]	Erdős, P. (1966) Some Recent Results on Extremal Problems in Graph Theory (Results). In: Theory of Graphs, 117-123.
[6]	Alon, N., Rónyai, L. and Szabó, T. (1999) Norm-Graphs: Variations and Applications. Journal of Combinatorial Theory, Series B, 76, 280-290. https://doi.org/10.1006/jctb.1999.1906
[7]	Kollár, J., Rónyai, L. and Szabó, T. (1996) Norm-Graphs and Bipartite Turán Numbers. Combinatorica, 16, 399-406. https://doi.org/10.1007/bf01261323
[8]	Füredi, Z. (1991) On a Turán Type Problem of Erdős. Combinatorica, 11, 75-79. https://doi.org/10.1007/bf01375476
[9]	Alon, N., Krivelevich, M. and Sudakov, B. (2003) Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions. Combinatorics, Probability and Computing, 12, 477-494. https://doi.org/10.1017/s0963548303005741
[10]	Gyárfás, A., Rousseau, C.C. and Schelp, R.H. (1984) An Extremal Problem for Paths in Bipartite Graphs. Journal of Graph Theory, 8, 83-95. https://doi.org/10.1002/jgt.3190080109
[11]	Li, X., Tu, J. and Jin, Z. (2009) Bipartite Rainbow Numbers of Matchings. Discrete Mathematics, 309, 2575-2578. https://doi.org/10.1016/j.disc.2008.05.011
[12]	Erdös, P., Sárközy, A. and Sós, V.T. (1995) On Product Representations of Powers, I. European Journal of Combinatorics, 16, 567-588. https://doi.org/10.1016/0195-6698(95)90039-x
[13]	N. Sárközy, G. (1995) Cycles in Bipartite Graphs and an Application in Number Theory. Journal of Graph Theory, 19, 323-331. https://doi.org/10.1002/jgt.3190190305
[14]	Györi, E. (1997) C6-Free Bipartite Graphs and Product Representation of Squares. Discrete Mathematics, 165, 371-375. https://doi.org/10.1016/s0012-365x(96)00184-7
[15]	Győri, E. (2006) Triangle-Free Hypergraphs. Combinatorics, Probability and Computing, 15, 185-191. https://doi.org/10.1017/s0963548305007108
[16]	Balbuena, C., García-Vázquez, P., Marcote, X. and Valenzuela, J.C. (2007) Counterexample to a Conjecture of Györi on C2l-Free Bipartite Graphs. Discrete Mathematics, 307, 748-749. https://doi.org/10.1016/j.disc.2006.07.003
[17]	Li, B. and Ning, B. (2021) Exact Bipartite Turán Numbers of Large Even Cycles. Journal of Graph Theory, 97, 642-656. https://doi.org/10.1002/jgt.22676
[18]	Jackson, B. (1985) Long Cycles in Bipartite Graphs. Journal of Combinatorial Theory, Series B, 38, 118-131. https://doi.org/10.1016/0095-8956(85)90077-2
[19]	Zarankiewicz, K. (1951) Problem P 101. Colloquium Mathematicum, 2, 301.
[20]	Goddard, W., Henning, M.A. and Oellermann, O.R. (2000) Bipartite Ramsey Numbers and Zarankiewicz Numbers. Discrete Mathematics, 219, 85-95. https://doi.org/10.1016/s0012-365x(99)00370-2
[21]	Griggs, J.R. and Ouyang, J. (1997) (0,1)-Matrices with No Half-Half Submatrix of Ones. European Journal of Combinatorics, 18, 751-761. https://doi.org/10.1006/eujc.1996.0133
[22]	Balbuena, C., García-Vázquez, P., Marcote, X. and Valenzuela, J.C. (2007) New Results on the Zarankiewicz Problem. Discrete Mathematics, 307, 2322-2327. https://doi.org/10.1016/j.disc.2006.11.002
[23]	Yang, Y. (2018) The Signless Laplacian Spectral Radius of Some Special Bipartite Graphs. Journal of Applied Mathematics and Physics, 6, 2159-2165. https://doi.org/10.4236/jamp.2018.610181
[24]	Wang, G. and Liu, G. (2012) Rainbow Matchings in Properly Colored Bipartite Graphs. Open Journal of Discrete Mathematics, 2, 62-64. https://doi.org/10.4236/ojdm.2012.22011