1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Extremal Graphs for Even Linear Forests in Bipartite Graphs

Published Online: 08 Oct 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 20 Sep 2020
Accepted: 03 Aug 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Zarankiewicz proposed the problem of determining the maximum number of edges in an (n, m)-bipartite graph containing no complete bipartite graph Ka,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

MSC 2010

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

[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/S096354831100046010.1017/S0963548311000460Search in Google Scholar

[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/BF0202449810.1007/BF02024498Search in Google Scholar

[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-510.1016/0095-8956(75)90080-5Search in Google Scholar

[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.10.1007/978-3-642-39286-3_7Search in Google Scholar

[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-510.1007/s00373-010-0999-5Search in Google Scholar

[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.319008010910.1002/jgt.3190080109Search in Google Scholar

[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-210.1016/0095-8956(81)90050-2Search in Google Scholar

[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.211110.7151/dmgt.2111Search in Google Scholar

[10] J.-Y. Li, S.-S. Li and J.-H. Yin, On Turán number for S1S2, Appl. Math. Comput. 385 (2020) 125400. https://doi.org/10.1016/j.amc.2020.12540010.1016/j.amc.2020.125400Search in Google Scholar

[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.01110.1016/j.disc.2008.05.011Search in Google Scholar

[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-x10.4153/CJM-1968-012-xSearch in Google Scholar

[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.Search in Google Scholar

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

[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.00410.1016/j.disc.2016.08.004Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo