On the Turán Numbers of Linear Forests in Bipartite Graphs

Abstract

A linear forest is a graph consisting of paths. In this paper, the authors determine the maximum number of edges in an (m, n)-bipartite graph which does not contain a linear forest consisting of paths on at least four vertices for n ≥ m when m is sufficiently large.

Keywords

Turán number / Linear forest / Bipartite graph / 05C35 / 05C05

References

[1] Erdős P, Gallai T. On maximal paths and circuits of graphs. Acta Math. Hungarica. 1959, 10(3): 337-356

[2] Gorgol I. Turán numbers for disjoint copies of graphs. Graphs Combin. 2011, 27: 661-667

[3] Bushaw N, Kettle N. Forbidding Multiple Copies of Forestable Graphs. Graphs Combin. 2020, 36: 459-467

[4] Bielak H, Kieliszek S. The Turán number of the graph 3P₄. Ann. Univ. Mariae Curie-Sklodowska Sect. A. 2014, 68(1): 21-29

[5] Bielak H, Kieliszek S. The Turán number of the graph 2P₅. Discuss. Math. Graph Theory. 2016, 36(3): 683-694

[6] Lan Y, Qin Z, Shi Y. The Turán number for 2P₇. Discuss. Math. Graph Theory. 2019, 39: 805-814

[7] Lidický B, Liu H, Palmer C. On the Turán number of forests. Electron. J. Comb. 2013, 20(2): 13 pp

[8] Yuan L, Zhang X. Turán numbers for disjoint paths. J. Graph Theory. 2021, 98(3): 499-524

[9] Gyárfás A, Rousseau C C, Schelp R H. An extremal problem for paths in bipartite graphs. J. Graph Theory. 1984, 8(1): 83-95

[10] Chen, M., Wang, N., Yuan, L. and Zhang, X., The bipartite Turán number and spectral extremum for linear forests, http://arxiv.org/abs/2201.00453v1.

[11] Jackson B. Cycles in bipartite graphs. J. Combin. Theory Ser. B. 1981, 30: 332-342

[12] Balister P N, Győri E, Lehel J, Schelp R H. Connected graphs without long paths. Discrete Math.. 2008, 308: 4487-4494

[13] Yuan L, Zhang X. The Turán number of disjoint copies of paths. Discrete Math.. 2017, 340(2): 132-139

[14] Yuan L, Zhang X. Extremal graphs for even linear forests in bipartite graphs. Discuss. Math. Graph Theory. 2024, 44(1): 5-16.

[15] Bushaw N, Kettle N. Turán numbers of multiple paths and equibipartite forests. Combin. Probab. Comput. 2011, 20: 837-853

[16] Faudree R J, Schelp R H. Path Ramsey numbers in multicolourings. J. Combin. Theory Ser. B. 1975, 19: 150-160

[17] Kopylov G N. On maximal paths and cycles in a graph. Soviet Math. Dokl. 1977, 18: 593-596