Caro and Yuster's maximum-degree repetition conjecture

For an integer $k$ at least $2$ and a graph $G$, let $n(G)$ denote the order of $G$. Define $f_k(G)$ as the minimum cardinality of a set $X$ of vertices of $G$ such that $G-X$ has either $k$ vertices of maximum degree or order less than $k$.

Caro and Yuster's conjecture. For every integer $k$ at least $2$, there is a constant $c_k$ such that

$$f_k(G)\leq c_k \sqrt{n(G)}$$

for every graph $G$.

The conjecture has the best possible growth rate in general: Caro and Yuster constructed graphs with $f_2(G)\geq (1-o(1))\sqrt{n(G)}$. They verified it for $k\in\{2,3\}$ and proved it for $C_4$-free graphs, while the general assertion remains open.