Geodesic
Extremal graphs for even linear forests in bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 5-16 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Zarankiewicz proposed the problem of determining the maximum number of edges in an (n,m)-bipartite graph containing no complete bipartite graph K_a,b. In this paper, we consider a variant of Zarankiewicz's problem and determine the maximum number of edges of an (n,m)-bipartite graph without containing a linear forest consisting of even paths. Moveover, all these extremal graphs are characterized in a recursion way.
Keywords: bipartite graph, linear forest, extremal graph, Tur\'{a}n number 
@article{DMGT_2024_44_1_a0,
     author = {Yuan, Long-Tu and Zhang, Xiao-Dong},
     title = {Extremal graphs for even linear forests in bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--16},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a0/}
}
TY  - JOUR
AU  - Yuan, Long-Tu
AU  - Zhang, Xiao-Dong
TI  - Extremal graphs for even linear forests in bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 5
EP  - 16
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a0/
LA  - en
ID  - DMGT_2024_44_1_a0
ER  - 
%0 Journal Article
%A Yuan, Long-Tu
%A Zhang, Xiao-Dong
%T Extremal graphs for even linear forests in bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 5-16
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a0/
%G en
%F DMGT_2024_44_1_a0
Yuan, Long-Tu; Zhang, Xiao-Dong. Extremal graphs for even linear forests in bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 5-16. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a0/

[1] H. Bielak and S. Kieliszek, The Turán number of the graph $ 2P_5 $, Discuss. Math. Graph Theory 36 (2016) 683–694. https://doi.org/10.7151/dmgt.1883

[2] N. Bushaw and N. Kettle, Turán numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20 (2011) 837–853. https://doi.org/10.1017/S0963548311000460

[3] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar 10 (1959) 337–356. https://doi.org/10.1007/BF02024498

[4] R.J. Faudree and R.H. Schelp, Path Ramsey numbers in multicolourings, J. Combin. Theory Ser. B 19 (1975) 150–160. https://doi.org/10.1016/0095-8956(75)90080-5

[5] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in: Erdős Centennial, Bolyai Soc. Math. Stud. 25, L. Lovász, I.Z. Ruzsa and V.T. Sós (Ed(s)), (Springer, Berlin 2013) 169–264.

[6] I. Gorgol, Turán numbers for disjoint copies of graphs, Graphs Combin. 27 (2011) 661–667. https://doi.org/10.1007/s00373-010-0999-5

[7] A. Gyárfás, C.C. Rousseau and R.H. Schelp, An extremal problem for paths in bipartite graphs, J. Graph Theory 8 (1984) 83–95. https://doi.org/10.1002/jgt.3190080109

[8] B. Jackson, Cycles in bipartite graphs, J. Combin. Theory Ser. B 30 (1981) 332–342. https://doi.org/10.1016/0095-8956(81)90050-2

[9] Y. Lan, Z. Qin and Y. Shi, The Turán number of 2P7, Discuss. Math. Graph Theory 39 (2019) 805–814. https://doi.org/10.7151/dmgt.2111

[10] J.-Y. Li, S.-S. Li and J.-H. Yin, On Turán number for $ S_{\mathcal{l}_1} \cup S_{\mathcal{l}_2} $, Appl. Math. Comput. 385 (2020) 125400. https://doi.org/10.1016/j.amc.2020.125400

[11] X. Li, J. Tua and Z. Jin, Bipartite rainbow numbers of matchings, Discrete Math. 309 (2009) 2575–2578. https://doi.org/10.1016/j.disc.2008.05.011

[12] J.W. Moon, On independent complete subgraphs in a graph, Canad. J. Math. 20 (1968) 95–102. https://doi.org/10.4153/CJM-1968-012-x

[13] M. Simonovits, A method for solving extremal problems in extremal graph theory, in: In Theory of Graphs, P. Erdős and G. Katona (Ed(s)), (Academic Press 1968) 279–319.

[14] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok. 48 (1941) 436–452, in Hungarian.

[15] L.T. Yuan and X.D. Zhang, The Turán number of disjoint copies of paths, Discrete Math. 340 (2017) 132–139. https://doi.org/10.1016/j.disc.2016.08.004

[16] K. Zarankiewicz, Problem 101, Colloq. Math. 2 (1951) 301–301.