Article in volume
Authors:
Title:
Extremal graphs for even linear forests in bipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 5-16
Received: 2020-09-20 , Revised: 2021-08-03 , Accepted: 2021-08-03 , Available online: 2021-08-24 , https://doi.org/10.7151/dmgt.2429
Abstract:
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án number
References:
- 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 - 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 - 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 - 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 - 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.
- 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 - 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 - 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 - Y. Lan, Z. Qin and Y. Shi, The Turán number of $2P_7$, Discuss. Math. Graph Theory 39 (2019) 805–814.
https://doi.org/10.7151/dmgt.2111 - J.-Y. Li, S.-S. Li and J.-H. Yin, On Turán number for $S_{\ell_1}\cup S_{\ell_2}$, Appl. Math. Comput. 385 (2020) 125400.
https://doi.org/10.1016/j.amc.2020.125400 - 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 - 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 - 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.
- P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok. 48 (1941) 436–452, in Hungarian.
- 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 - K. Zarankiewicz, Problem $101$, Colloq. Math. 2 (1951) 301–301.
Close