About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Lin, Jing
Maximum bipartite subgraphs in $H$-free graphs. (English). Czechoslovak Mathematical Journal, vol. 72 (2022), issue 3, pp. 621-635
MSC: 05C35, 05C70 | MR 4467931 | Zbl 07584091 | DOI: 10.21136/CMJ.2022.0302-20
Keywords:
bipartite subgraph; $H$-free; partition
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).
References:
[1] Alon, N.: Bipartite subgraphs. Combinatorica 16 (1996), 301-311. DOI 10.1007/BF01261315 | MR 1417340 | Zbl 0860.05043
[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. DOI 10.1016/S0095-8956(03)00036-4 | MR 1983363 | Zbl 1030.05060
[3] Alon, N., Halperin, E.: Bipartite subgraphs of integer weighted graphs. Discrete Math. 181 (1998), 19-29. DOI 10.1016/S0012-365X(97)00041-1 | MR 1600727 | Zbl 0903.05028
[4] Alon, N., Krivelevich, M., Sudakov, B.: MaxCut in $H$-free graphs. Comb. Probab. Comput. 14 (2005), 629-647. DOI 10.1017/S0963548305007017 | MR 2174649 | Zbl 1081.05047
[5] Bollobás, B., Scott, A. D.: Better bounds for Max Cut. Contemporary Combinatorics Bolyai Society Mathematical Studies 10. Springer, Berlin (2002), 185-246. MR 1919571 | Zbl 1014.90082
[6] Bollobás, B., Scott, A. D.: Problems and results on judicious partitions. Random Struct. Algorithms 21 (2002), 414-430. DOI 10.1002/rsa.10062 | MR 1945378 | Zbl 1013.05059
[7] Conlon, D., Lee, J., Janzer, O.: More on the extremal number of subdivisions. Combinatorica 41 (2021), 465-494. DOI 10.1007/s00493-020-4202-1 | MR 4328719 | Zbl 07413845
[8] Edwards, C. S.: Some extremal properties of bipartite subgraphs. Can. J. Math. 25 (1973), 475-485. DOI 10.4153/CJM-1973-048-x | MR 0337686 | Zbl 0254.05116
[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. MR 0398888 | Zbl 0326.05115
[10] Erdős, P., Gallai, T.: On maximal paths and circuits in graphs. Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. DOI 10.1007/BF02024498 | MR 0114772 | Zbl 0090.39401
[11] Erdős, P., Gyárfás, A., Kohayakawa, Y.: The size of the largest bipartite subgraphs. Discrete Math. 177 (1997), 267-271. DOI 10.1016/S0012-365X(97)00004-6 | MR 1483451 | Zbl 0888.05035
[12] Faudree, R. J., Simonovits, M.: On a class of degenerate extremal graph problems. Combinatorica 3 (1983), 83-93. DOI 10.1007/BF02579343 | MR 0716423 | Zbl 0521.05037
[13] Janzer, O.: Improved bounds for the extremal number of subdivisions. Electron. J. Comb. 26 (2019), Article ID P3.3, 6 pages. DOI 10.37236/8262 | MR 3982312 | Zbl 1416.05152
[14] Jensen, T. R., Toft, B.: Graph Coloring Problems. John Wiley & Sons, New York (1995). DOI 10.1002/9781118032497 | MR 1304254 | Zbl 0855.05054
[15] Li, Y., Rousseau, C. C., Zang, W.: Asymptotic upper bounds for Ramsey functions. Graphs Comb. 17 (2001), 123-128. DOI 10.1007/s003730170060 | MR 1828633 | Zbl 0979.05078
[16] Poljak, S., Tuza, Z.: Bipartite subgraphs of triangle-free graphs. SIAM J. Discrete Math. 7 (1994), 307-313. DOI 10.1137/S0895480191196824 | MR 1272003 | Zbl 0806.68086
[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. DOI 10.1017/CBO9780511734885.006 | MR 2187736 | Zbl 1110.05084
[18] Shearer, J. B.: A note on bipartite subgraphs of triangle-free graphs. Random Struct. Algorithms 3 (1992), 223-226. DOI 10.1002/rsa.3240030211 | MR 1151364 | Zbl 0765.05057
[19] Shearer, J. B.: On the independence number of sparse graphs. Random Struct. Algorithms 7 (1995), 269-271. DOI 10.1002/rsa.3240070305 | MR 1369066 | Zbl 0834.05030
[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).
[21] Zeng, Q., Hou, J.: Bipartite subgraphs of $H$-free graphs. Bull. Aust. Math. Soc. 96 (2017), 1-13. DOI 10.1017/S0004972716001295 | MR 3668394 | Zbl 1367.05110
[22] Zeng, Q., Hou, J.: Maximum cuts of graphs with forbidden cycles. Ars Math. Contemp. 15 (2018), 147-160. DOI 10.26493/1855-3974.1218.5ed | MR 3862083 | Zbl 1404.05092
Partner of
EuDML logo