| 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 |
| . |
