Caro, Lauri, and Zarb's forest bound conjecture for f2f_2

About 9 years old · traced to

Let tt be a positive integer and let FF be a forest. For a graph GG, let fk(G)f_k(G) be the minimum cardinality of a set XX of vertices of GG such that G−XG-X has either kk vertices of maximum degree or order less than kk.

Caro, Lauri, and Zarb's conjecture. If FF has order at most

16(t3+6t2+17t+12),\frac{1}{6}\left(t^3+6t^2+17t+12\right),

then

f2(F)≤t.f_2(F)\leq t.

This is a precise conjecture for forests that improves the known general forest bound and was constructed to be tight by matching examples. The paper states that it verifies this conjecture.

References

Primary source

M. Fürst, M. Gentner, M. A. Henning, S. Jäger and D. Rautenbach, “Equating k Maximum Degrees in Graphs without Short Cycles”, arXiv:1705.07409 (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.