TY - JOUR
T1 - On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs
AU - Balogh, József
AU - Keevash, Peter
AU - Sudakov, Benny
N1 - Funding Information:
E-mail addresses: [email protected] (J. Balogh), [email protected] (P. Keevash), [email protected] (B. Sudakov). 1 Research supported in part by NSF grant DMS-0302804 and OTKA grant 049398. Part of this research was done while visiting the Institute for Advanced Study at Princeton. 2 Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA–Israeli BSF grant, and by an Alfred P. Sloan fellowship.
PY - 2006/11
Y1 - 2006/11
N2 - Erdo{combining double acute accent}s posed the problem of finding conditions on a graph G that imply t (G) = b (G), where t (G) is the largest number of edges in a triangle-free subgraph and b (G) is the largest number of edges in a bipartite subgraph. Let δc be the least number so that any graph G on n vertices with minimum degree δc n has t (G) = b (G). Extending results of Bondy, Shen, Thomassé and Thomassen we show that 0.75 ≤ δc < 0.791.
AB - Erdo{combining double acute accent}s posed the problem of finding conditions on a graph G that imply t (G) = b (G), where t (G) is the largest number of edges in a triangle-free subgraph and b (G) is the largest number of edges in a bipartite subgraph. Let δc be the least number so that any graph G on n vertices with minimum degree δc n has t (G) = b (G). Extending results of Bondy, Shen, Thomassé and Thomassen we show that 0.75 ≤ δc < 0.791.
KW - Extremal Graphs Theory
KW - Triangle-free graphs
KW - Turán's theorem
UR - http://www.scopus.com/inward/record.url?scp=33845263637&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33845263637&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2006.03.001
DO - 10.1016/j.jctb.2006.03.001
M3 - Article
AN - SCOPUS:33845263637
SN - 0095-8956
VL - 96
SP - 919
EP - 932
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 6
ER -