Akbari et al.'s Caro–Wei bound for induced linear forests

All graphs are finite, simple, and undirected; for a graph GG, let V(G)V(G) be its vertex set and let d(v)d(v) denote the degree of vv. A linear forest is a forest in which every component is a path. If GG has minimum degree at least 22, then Akbari et al.'s conjecture. GG has an induced linear forest with at least

vV(G)2d(v)+1\sum_{v\in V(G)} \frac{2}{d(v)+1}

vertices. This conjecture strengthens the k=1k=1 case of the Alon–Kahn–Seymour bound, which guarantees an induced forest of this order but does not require its components to be paths. The conjecture is the motivating statement of the paper; the supplied text gives no evidence that it has been resolved.

Sources & referencesView supporting material

Primary source

Gwenaël Joret and Robin Petit, “A Caro-Wei bound for induced linear forests in graphs”, arXiv:2403.17568 (2025).

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.