Forest maximum-degree repetition conjecture

Let FF be a forest on nn vertices, and let f(F)=f2(F)f(F)=f_2(F) denote the minimum number of vertices that must be deleted to obtain an induced subgraph with at least two vertices attaining its maximum degree, or with fewer than two vertices. Forest conjecture. If

nt3+6t2+17t+126,n\leq\frac{t^3+6t^2+17t+12}{6},

then f(F)tf(F)\leq t, and this bound is sharp. This conjecture concerns the extremal value of the deletion parameter for forests; the supplied text does not establish it, so its resolution remains open.

Sources & referencesView supporting material

Primary source

Yair Caro, Josef Lauri and Christina Zarb, “Equating two maximum degrees”, arXiv:1704.08472 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.