Initiated by a recent question of Erdhos, we give lower bounds on the size of a largest k-partite subgraph of a graph. Also, the corresponding problem for uniform hypergraphs is considered.
