ON WEAKLY TURAN-GOOD GRAPHS

被引:1
|
作者
Gerbner, Daniel [1 ]
机构
[1] Alfred Renyi Inst Math, Budapest, Hungary
关键词
generalized Turan problem; extremal; Turan-good; NUMBER;
D O I
10.7151/dmgt.2510
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given graphs H and F with chi(H)<chi(F), we say that H is weakly F-Tur & aacute;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 & aacute;n-good, improving a very recent asymptotic bound due to Grzesik, Gyori, Salia and Tompkins. They also showed that for any r there exist graphs that are not weakly K-r-Tur & aacute;n-good. We show that for any non-bipartite F there exists graphs that are not weakly F-Tur & aacute;n-good. We also show examples of graphs that are C2k+1-Tur & aacute;n-good but not C2 & ell;+1-Tur & aacute;n-good for every k>& ell;.
引用
收藏
页码:1539 / 1550
页数:12
相关论文
共 13 条
  • [1] Every graph is eventually Turan-good
    Morrison, Natasha
    Nir, J. D.
    Norin, Sergey
    Rzazewski, Pawel
    Wesolek, Alexandra
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2023, 162 : 231 - 243
  • [2] Some results on k-Turan-good graphs
    Qian, Bingchen
    Xie, Chengfei
    Ge, Gennian
    DISCRETE MATHEMATICS, 2021, 344 (09)
  • [3] Generalized Turan Problems for Small Graphs
    Gerbner, Daniel
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (02) : 549 - 572
  • [4] An Extremal Property of Turan Graphs
    Lazebnik, Felix
    Tofts, Spencer
    ELECTRONIC JOURNAL OF COMBINATORICS, 2010, 17 (01)
  • [5] On Turan densities of small triple graphs
    Shi, Lingsheng
    EUROPEAN JOURNAL OF COMBINATORICS, 2016, 52 : 95 - 102
  • [6] An Extremal Property of Turan Graphs, II
    Tofts, Spencer N.
    JOURNAL OF GRAPH THEORY, 2014, 75 (03) : 275 - 283
  • [7] A generalized Turan problem in random graphs
    Samotij, Wojciech
    Shikhelman, Clara
    RANDOM STRUCTURES & ALGORITHMS, 2020, 56 (02) : 283 - 305
  • [8] A Turan-Type Problem on Distances in Graphs
    Tyomkyn, Mykhaylo
    Uzzell, Andrew J.
    GRAPHS AND COMBINATORICS, 2013, 29 (06) : 1927 - 1942
  • [9] Random polynomial graphs for random Turan problems
    Spiro, Sam
    JOURNAL OF GRAPH THEORY, 2024, 105 (02) : 192 - 208
  • [10] Turan and Ramsey Properties of Subcube Intersection Graphs
    Johnson, J. Robert
    Markstrom, Klas
    COMBINATORICS PROBABILITY & COMPUTING, 2013, 22 (01) : 55 - 70