On the minimal degree condition of graphs implying equality of the largest Kr-free subgraphs and (r − 1)-partite subgraphs.

Erdős posed the problem of finding conditions on a graph G which imply that the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We consider a more general problem by defining δ r to be the least number so that any graph G on n vertices with minimum degree δ r n has the property that the largest number of edges in an (r − 1) -partite subgraph equals to the largest number of edges in a K r -free subgraph. We show that 3 r − 4 3 r − 1 < δ r ≤ 4 (3 r − 7) (r − 1) + 1 4 (r − 2) (3 r − 4) when r ≥ 4. We also show δ 4 ≤ 0.9415. [ABSTRACT FROM AUTHOR]