Previous |  Up |  Next

Article

Title: Maximum bipartite subgraphs in $H$-free graphs (English)
Author: Lin, Jing
Language: English
Journal: Czechoslovak Mathematical Journal
ISSN: 0011-4642 (print)
ISSN: 1572-9141 (online)
Volume: 72
Issue: 3
Year: 2022
Pages: 621-635
Summary lang: English
.
Category: math
.
Summary: Given a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. In this paper we prove that $f(m,\theta _{k,s})\geq \tfrac 12 m +\Omega (m^{(2k+1)/(2k+2)})$, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write $K'_{k}$ and $K'_{t,s}$ for the subdivisions of $K_k$ and $K_{t,s}$. We show that $f(m,K'_{k})\geq \tfrac 12 m +\Omega (m^{(5k-8)/(6k-10)})$ and $f(m,K'_{t,s})\geq \tfrac 12 m +\Omega (m^{(5t-1)/(6t-2)})$, improving a result of Q. Zeng, J. Hou. We also give lower bounds on wheel-free graphs. All of these contribute to a conjecture of N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov (2003). (English)
Keyword: bipartite subgraph
Keyword: $H$-free
Keyword: partition
MSC: 05C35
MSC: 05C70
idZBL: Zbl 07584091
idMR: MR4467931
DOI: 10.21136/CMJ.2022.0302-20
.
Date available: 2022-08-22T08:15:04Z
Last updated: 2024-10-04
Stable URL: http://hdl.handle.net/10338.dmlcz/150605
.
Reference: [1] Alon, N.: Bipartite subgraphs.Combinatorica 16 (1996), 301-311. Zbl 0860.05043, MR 1417340, 10.1007/BF01261315
Reference: [2] Alon, N., Bollobás, B., Krivelevich, M., Sudakov, B.: Maximum cuts and judicious partitions in graphs without short cycles.J. Comb. Theory, Ser. B 88 (2003), 329-346. Zbl 1030.05060, MR 1983363, 10.1016/S0095-8956(03)00036-4
Reference: [3] Alon, N., Halperin, E.: Bipartite subgraphs of integer weighted graphs.Discrete Math. 181 (1998), 19-29. Zbl 0903.05028, MR 1600727, 10.1016/S0012-365X(97)00041-1
Reference: [4] Alon, N., Krivelevich, M., Sudakov, B.: MaxCut in $H$-free graphs.Comb. Probab. Comput. 14 (2005), 629-647. Zbl 1081.05047, MR 2174649, 10.1017/S0963548305007017
Reference: [5] Bollobás, B., Scott, A. D.: Better bounds for Max Cut.Contemporary Combinatorics Bolyai Society Mathematical Studies 10. Springer, Berlin (2002), 185-246. Zbl 1014.90082, MR 1919571
Reference: [6] Bollobás, B., Scott, A. D.: Problems and results on judicious partitions.Random Struct. Algorithms 21 (2002), 414-430. Zbl 1013.05059, MR 1945378, 10.1002/rsa.10062
Reference: [7] Conlon, D., Lee, J., Janzer, O.: More on the extremal number of subdivisions.Combinatorica 41 (2021), 465-494. Zbl 07413845, MR 4328719, 10.1007/s00493-020-4202-1
Reference: [8] Edwards, C. S.: Some extremal properties of bipartite subgraphs.Can. J. Math. 25 (1973), 475-485. Zbl 0254.05116, MR 0337686, 10.4153/CJM-1973-048-x
Reference: [9] Edwards, C. S.: An improved lower bound for the number of edges in a largest bipartite subgraph.Recent Advances in Graph Theory Academia, Prague (1975), 167-181. Zbl 0326.05115, MR 0398888
Reference: [10] Erdős, P., Gallai, T.: On maximal paths and circuits in graphs.Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. Zbl 0090.39401, MR 0114772, 10.1007/BF02024498
Reference: [11] Erdős, P., Gyárfás, A., Kohayakawa, Y.: The size of the largest bipartite subgraphs.Discrete Math. 177 (1997), 267-271. Zbl 0888.05035, MR 1483451, 10.1016/S0012-365X(97)00004-6
Reference: [12] Faudree, R. J., Simonovits, M.: On a class of degenerate extremal graph problems.Combinatorica 3 (1983), 83-93. Zbl 0521.05037, MR 0716423, 10.1007/BF02579343
Reference: [13] Janzer, O.: Improved bounds for the extremal number of subdivisions.Electron. J. Comb. 26 (2019), Article ID P3.3, 6 pages. Zbl 1416.05152, MR 3982312, 10.37236/8262
Reference: [14] Jensen, T. R., Toft, B.: Graph Coloring Problems.John Wiley & Sons, New York (1995). Zbl 0855.05054, MR 1304254, 10.1002/9781118032497
Reference: [15] Li, Y., Rousseau, C. C., Zang, W.: Asymptotic upper bounds for Ramsey functions.Graphs Comb. 17 (2001), 123-128. Zbl 0979.05078, MR 1828633, 10.1007/s003730170060
Reference: [16] Poljak, S., Tuza, Z.: Bipartite subgraphs of triangle-free graphs.SIAM J. Discrete Math. 7 (1994), 307-313. Zbl 0806.68086, MR 1272003, 10.1137/S0895480191196824
Reference: [17] Scott, A.: Judicious partitions and related problems.Surveys in Combinatorics 2005 London Mathematical Society Lecture Note Series 327. Cambridge University Press, Cambridge (2005), 95-117. Zbl 1110.05084, MR 2187736, 10.1017/CBO9780511734885.006
Reference: [18] Shearer, J. B.: A note on bipartite subgraphs of triangle-free graphs.Random Struct. Algorithms 3 (1992), 223-226. Zbl 0765.05057, MR 1151364, 10.1002/rsa.3240030211
Reference: [19] Shearer, J. B.: On the independence number of sparse graphs.Random Struct. Algorithms 7 (1995), 269-271. Zbl 0834.05030, MR 1369066, 10.1002/rsa.3240070305
Reference: [20] Wei, V.: A lower bound on the stability number of a simple graph.Technical Report 81-11217-9 Bell Laboratories Technical Memorandum, New Jersey (1981).
Reference: [21] Zeng, Q., Hou, J.: Bipartite subgraphs of $H$-free graphs.Bull. Aust. Math. Soc. 96 (2017), 1-13. Zbl 1367.05110, MR 3668394, 10.1017/S0004972716001295
Reference: [22] Zeng, Q., Hou, J.: Maximum cuts of graphs with forbidden cycles.Ars Math. Contemp. 15 (2018), 147-160. Zbl 1404.05092, MR 3862083, 10.26493/1855-3974.1218.5ed
.

Files

Files Size Format View
CzechMathJ_72-2022-3_1.pdf 274.1Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo