Geodesic
On weakly Turán-good graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1539-1550 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Given graphs H and F with χ(H) lt;χ(F), we say that H is weakly F-Turán-good if among n-vertex F-free graphs, a (χ(F)-1)-partite graph contains the most copies of H. Let H be a bipartite graph that contains a complete bipartite subgraph K such that each vertex of H is adjacent to a vertex of K. We show that H is weakly K_3-Turán-good, improving a very recent asymptotic bound due to Grzesik, Győri, Salia and Tompkins. They also showed that for any r there exist graphs that are not weakly K_r-Turán-good. We show that for any non-bipartite F there exist graphs that are not weakly F-Turán-good. We also show examples of graphs that are C_2k+1-Turán-good but not C_2ℓ+1-Turán-good for every k gt;ℓ.
Keywords: generalized Tur\'an problem, extremal, Tur\'an-good 
@article{DMGT_2024_44_4_a15,
     author = {Gerbner, D\'aniel},
     title = {On weakly {Tur\'an-good} graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1539--1550},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a15/}
}
TY  - JOUR
AU  - Gerbner, Dániel
TI  - On weakly Turán-good graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1539
EP  - 1550
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a15/
LA  - en
ID  - DMGT_2024_44_4_a15
ER  - 
%0 Journal Article
%A Gerbner, Dániel
%T On weakly Turán-good graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1539-1550
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a15/
%G en
%F DMGT_2024_44_4_a15
Gerbner, Dániel. On weakly Turán-good graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1539-1550. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a15/

[1] N. Alon and C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172. https://doi.org/10.1016/j.jctb.2016.03.004

[2] J.I. Brown and A. Sidorenko, The inducibility of complete bipartite graphs, J. Graph Theory 18 (1994) 629–645. https://doi.org/10.1002/jgt.3190180610

[3] P. Erdős, Some recent results on extremal problems in graph theory (Results), in: Theory of Graphs, Rosentstiehl (Ed(s)), (Gordon and Breach, New York 1967) 117–123.

[4] P. Erdős, On some new inequalities concerning extremal properties of graphs, in: Theory of Graphs, P. Erdős and G.O.H. Katona (Ed(s)), (Academic Press, New York 1968) 77–81.

[5] P. Erdős, P. Frankl and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986) 113–121. https://doi.org/10.1007/BF01788085

[6] P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51–57.

[7] P. Erdős and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946) 1087–1091. https://doi.org/10.1090/S0002-9904-1946-08715-7

[8] D. Gerbner, On Turán-good graphs, Discrete Math. 344 (2021) 112445. https://doi.org/10.1016/j.disc.2021.112445

[9] D. Gerbner, Generalized Turán problems for small graphs, Discuss. Math. Graph Theory 43 (2023) 549–572. https://doi.org/10.7151/dmgt.2388

[10] D. Gerbner, Generalized Turán problems for double stars, Discrete Math. 346(7) (2023) 113395. https://doi.org/10.1016/j.disc.2023.113395

[11] D. Gerbner, Some stability and exact results in generalized Turán problems, Studia Sci. Math. Hungar. 60 (2023) 16–26. https://doi.org/10.1556/012.2023.01533

[12] D. Gerbner, Paths are Turán-good, Graphs Combin. 39 (2023) 56. https://doi.org/10.1007/s00373-023-02641-z

[13] D. Gerbner and C. Palmer, Counting copies of a fixed subgraph in F-free graphs, European J. Combin. 82 (2019) 103001. https://doi.org/10.1016/j.ejc.2019.103001

[14] D. Gerbner and C. Palmer, Some exact results for generalized Turán problems, European J. Combin. 103 (2022) 103519. https://doi.org/10.1016/j.ejc.2022.103519

[15] A. Grzesik, E. Győri, N. Salia and C. Tompkins, Subgraph densities in Kr-free graphs, Electron. J. Combin. 30(1) (2023) #P1.51. https://doi.org/10.37236/11329

[16] E. Győri, J. Pach and M. Simonovits, On the maximal number of certain subgraphs in Kr-free graphs, Graphs Combin. 7 (1991) 31–37. https://doi.org/10.1007/BF01789461

[17] E. Győri, R. Wang and S. Woolfson, Extremal problems of double stars, Discrete Math. Theor. Comput. Sci. 24(2) (2023) 4. https://doi.org/10.46298/dmtcs.8499

[18] D. Hei, X. Hou and B. Liu, Some exact results of the generalized Turán numbers for paths, European J. Combin. 110 (2023) 103682. https://doi.org/10.1016/j.ejc.2022.103682

[19] J. Ma and Y. Qiu, Some sharp results on the generalized Turán numbers, European J. Combin. 84 (2020) 103206. https://doi.org/10.1016/j.ejc.2019.103026

[20] K. Murphy and J.D. Nir, Paths of length three are Kr+1-Turán-good, Electron. J. Combin. 28(4) (2021) #P4.34. https://doi.org/10.37236/10225

[21] B. Qian, C. Xie and G. Ge, Some results on k-Turán-good graphs, Discrete Math. 344(9) (2021) 112509. https://doi.org/10.1016/j.disc.2021.112509

[22] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Graphs, P. Erdös and G.O.H. Katona Ed(s)), (Academic Press, New York 1968) 279–319.

[23] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, Discrete Math. 7 (1974) 349–376. https://doi.org/10.1016/0012-365X(74)90044-2

[24] P. Turán, Egy gráfelméleti szélsőérték-feladatról, Mat. Fiz. Lapok 48 (1941) 436–452.

[25] A.A. Zykov, On some properties of linear complexes, Mat. Sb. 24(66) (1949) 163–188.