Geodesic
Maximum bipartite subgraphs in $H$-free graphs
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 3, pp. 621-635
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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).
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).
DOI : 10.21136/CMJ.2022.0302-20
Classification : 05C35, 05C70
Keywords: bipartite subgraph; $H$-free; partition 
@article{10_21136_CMJ_2022_0302_20,
     author = {Lin, Jing},
     title = {Maximum bipartite subgraphs in $H$-free graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {621--635},
     year = {2022},
     volume = {72},
     number = {3},
     doi = {10.21136/CMJ.2022.0302-20},
     mrnumber = {4467931},
     zbl = {07584091},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0302-20/}
}
TY  - JOUR
AU  - Lin, Jing
TI  - Maximum bipartite subgraphs in $H$-free graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2022
SP  - 621
EP  - 635
VL  - 72
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0302-20/
DO  - 10.21136/CMJ.2022.0302-20
LA  - en
ID  - 10_21136_CMJ_2022_0302_20
ER  - 
%0 Journal Article
%A Lin, Jing
%T Maximum bipartite subgraphs in $H$-free graphs
%J Czechoslovak Mathematical Journal
%D 2022
%P 621-635
%V 72
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0302-20/
%R 10.21136/CMJ.2022.0302-20
%G en
%F 10_21136_CMJ_2022_0302_20
Lin, Jing. Maximum bipartite subgraphs in $H$-free graphs. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 3, pp. 621-635. doi: 10.21136/CMJ.2022.0302-20

[1] Alon, N.: Bipartite subgraphs. Combinatorica 16 (1996), 301-311. | DOI | MR | JFM

[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 | MR | JFM

[3] Alon, N., Halperin, E.: Bipartite subgraphs of integer weighted graphs. Discrete Math. 181 (1998), 19-29. | DOI | MR | JFM

[4] Alon, N., Krivelevich, M., Sudakov, B.: MaxCut in $H$-free graphs. Comb. Probab. Comput. 14 (2005), 629-647. | DOI | MR | JFM

[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 | JFM

[6] Bollobás, B., Scott, A. D.: Problems and results on judicious partitions. Random Struct. Algorithms 21 (2002), 414-430. | DOI | MR | JFM

[7] Conlon, D., Lee, J., Janzer, O.: More on the extremal number of subdivisions. Combinatorica 41 (2021), 465-494. | DOI | MR | JFM

[8] Edwards, C. S.: Some extremal properties of bipartite subgraphs. Can. J. Math. 25 (1973), 475-485. | DOI | MR | JFM

[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 | JFM

[10] Erdős, P., Gallai, T.: On maximal paths and circuits in graphs. Acta Math. Acad. Sci. Hung. 10 (1959), 337-356. | DOI | MR | JFM

[11] Erdős, P., Gyárfás, A., Kohayakawa, Y.: The size of the largest bipartite subgraphs. Discrete Math. 177 (1997), 267-271. | DOI | MR | JFM

[12] Faudree, R. J., Simonovits, M.: On a class of degenerate extremal graph problems. Combinatorica 3 (1983), 83-93. | DOI | MR | JFM

[13] Janzer, O.: Improved bounds for the extremal number of subdivisions. Electron. J. Comb. 26 (2019), Article ID P3.3, 6 pages. | DOI | MR | JFM

[14] Jensen, T. R., Toft, B.: Graph Coloring Problems. John Wiley & Sons, New York (1995). | DOI | MR | JFM

[15] Li, Y., Rousseau, C. C., Zang, W.: Asymptotic upper bounds for Ramsey functions. Graphs Comb. 17 (2001), 123-128. | DOI | MR | JFM

[16] Poljak, S., Tuza, Z.: Bipartite subgraphs of triangle-free graphs. SIAM J. Discrete Math. 7 (1994), 307-313. | DOI | MR | JFM

[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 | MR | JFM

[18] Shearer, J. B.: A note on bipartite subgraphs of triangle-free graphs. Random Struct. Algorithms 3 (1992), 223-226. | DOI | MR | JFM

[19] Shearer, J. B.: On the independence number of sparse graphs. Random Struct. Algorithms 7 (1995), 269-271. | DOI | MR | JFM

[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 | MR | JFM

[22] Zeng, Q., Hou, J.: Maximum cuts of graphs with forbidden cycles. Ars Math. Contemp. 15 (2018), 147-160. | DOI | MR | JFM

Cité par Sources :