Article in press
Authors:
Title:
On weakly Turán-good graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-12-27 , Revised: 2023-07-04 , Accepted: 2023-07-07 , Available online: 2023-08-22 , https://doi.org/10.7151/dmgt.2510
Abstract:
Given graphs $H$ and $F$ with $\chi(H)<\chi(F)$, we say that $H$ is weakly
$F$-Turán-good if among $n$-vertex $F$-free graphs, a $(\chi(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\ell+1}$-Turán-good for every $k>\ell$.
Keywords:
generalized Turán problem, extremal, Turán-good
References:
- 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 - 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 - 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.
- 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.
- 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 - P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51–57.
- 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 - D. Gerbner, On Turán-good graphs, Discrete Math. 344 (2021) 112445.
https://doi.org/10.1016/j.disc.2021.112445 - D. Gerbner, Generalized Turán problems for small graphs, Discuss. Math. Graph Theory 43 (2023) 549–572.
https://doi.org/10.7151/dmgt.2388 - D. Gerbner, Generalized Turán problems for double stars, Discrete Math. 346(7) (2023) 113395.
https://doi.org/10.1016/j.disc.2023.113395 - 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 - D. Gerbner, Paths are Turán-good, Graphs Combin. 39 (2023) 56.
https://doi.org/10.1007/s00373-023-02641-z - 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 - 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 - A. Grzesik, E. Győri, N. Salia and C. Tompkins, Subgraph densities in $K_r$-free graphs, Electron. J. Combin. 30(1) (2023) #P1.51.
https://doi.org/10.37236/11329 - E. Győri, J. Pach and M. Simonovits, On the maximal number of certain subgraphs in $K_r$-free graphs, Graphs Combin. 7 (1991) 31–37.
https://doi.org/10.1007/BF01789461 - 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 - 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 - 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 - K. Murphy and J.D. Nir, Paths of length three are $K_{r+1}$-Turán-good, Electron. J. Combin. 28(4) (2021) #P4.34.
https://doi.org/10.37236/10225 - 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 - 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.
- 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 - P. Turán, Egy gráfelméleti szélsőérték-feladatról, Mat. Fiz. Lapok 48 (1941) 436–452.
- A.A. Zykov, On some properties of linear complexes, Mat. Sb. 24(66) (1949) 163–188.
Close