Equating κ maximum degrees in graphs without short cycles

For an integer k at least 2, and a graph G, let fk (G) be 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 [Discrete Mathematics 310 (2010) 742-747] conjectured that, for every k, there is a constant ck such that fk (G) ≤ ck √ n(G) for every graph G. Verifying a conjecture of Caro, Lauri, and Zarb [arXiv:1704.08472v1], we show the best possible result that, if t is a positive integer, and F is a forest of order at most 1/6 (t3 + 6t2 + 17t + 12), then f2 (F) ≤ t. We study f3 (F) for forests F in more detail obtaining similar almost tight results, and we establish upper bounds on fk (G) for graphs G of girth at least 5. For graphs G of girth more than 2p, for p at least 3, our results imply fk (G) = O (n(G) p+1/ 3p). Finally, we show that, for every fixed k, and every given forest F, the value of fk (F) can be determined in polynomial time.