Large induced subgraphs with equated maximum degree

For a graph GG, denote by fk(G)fk(G) the smallest number of vertices that must be deleted from GG so that the remaining induced subgraph has its maximum degree shared by at least kk vertices. It is not difficult to prove that there are graphs for which already f2(G)≥n(1−o(1)), where nn is the number of vertices of GG. It is conjectured that fk(G)=Θ(n) for every   fixed kk. We prove this for k=2,3k=2,3. While the proof for the case k=2k=2 is easy, already the proof for the case k=3k=3 is considerably more difficult. The case k=4k=4 remains open.A related parameter, sk(G)sk(G), denotes the maximum integer mm so that there are kk vertex-disjoint subgraphs of GG, each with mm vertices, and with the same   maximum degree. We prove that for every fixed kk, sk(G)≥n/k−o(n)sk(G)≥n/k−o(n). The proof relies on probabilistic arguments.