Graphs with no induced K2,t

被引:5
作者
Illingworth, Freddie [1 ]
机构
[1] Univ Cambridge, Dept Pure Math & Math Stat, Cambridge, England
基金
英国工程与自然科学研究理事会;
关键词
NUMBER;
D O I
10.37236/9223
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Consider a graph G on n vertices with alpha((n)(2)) edges which does not contain an induced K-2,K-t (t >= 2). How large must alpha be to ensure that G contains, say, a large clique or some fixed subgraph H? We give results for two regimes: for alpha bounded away from zero and for alpha = o(1). Our results for alpha = o(1) are strongly related to the Induced Turan numbers which were recently introduced by Loh, Tait, Timmons and Zhou. For alpha bounded away from zero, our results can be seen as a generalisation of a result of Gyarfas, Hubenko and Solymosi and more recently Holmsen (whose argument inspired ours).
引用
收藏
页码:1 / 11
页数:11
相关论文
共 10 条
[1]  
[Anonymous], 2001, CAMBRIDGE STUDIES AD
[2]   ON THE STRUCTURE OF LINEAR GRAPHS [J].
ERDOS, P ;
STONE, AH .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091
[3]  
Erdos P., 1935, Compos. Math, V2, P463
[4]  
Erdos P., 1966, Studia Scientiarum Mathematicarum Hungarica, V1, P51
[5]   Turan Number of an Induced Complete Bipartite Graph Plus an Odd Cycle [J].
Ergemlidze, Beka ;
Gyori, Ervin ;
Methuku, Abhishek .
COMBINATORICS PROBABILITY & COMPUTING, 2019, 28 (02) :241-252
[6]   New asymptotics for bipartite Turan numbers [J].
Furedi, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 75 (01) :141-144
[7]  
Gyárfás A, 2002, COMBINATORICA, V22, P269, DOI 10.1007/s004930200012
[8]   Large Cliques in Hypergraphs with Forbidden Substructures [J].
Holmsen, Andreas F. .
COMBINATORICA, 2020, 40 (04) :527-537
[9]  
Loh P.-S., 2017, COMB PROBAB COMPUT, V27, P1
[10]   A NOTE ON THE INDEPENDENCE NUMBER OF TRIANGLE-FREE GRAPHS [J].
SHEARER, JB .
DISCRETE MATHEMATICS, 1983, 46 (01) :83-87