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: | 2022-12-27 |
| 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 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
