Matsuda–Ozeki–Yamashita's branch-vertex conjecture for claw-free graphs

About 8 years old · traced to

Let kk be a non-negative integer and let GG be a connected claw-free graph of order nn. For an integer r≥2r\geq 2, let σr(G)\sigma_r(G) be the minimum degree sum of an independent set of rr vertices in GG:

σr(G)=min⁡{∑x∈Sdeg⁡G(x):S⊆V(G), ∣S∣=r, S is independent}.\sigma_r(G)=\min\left\{\sum_{x\in S}\deg_G(x): S\subseteq V(G),\ |S|=r,\ S\text{ is independent}\right\}.

A vertex of degree at least three in a tree is called a branch vertex. Matsuda–Ozeki–Yamashita's conjecture. Let kk be a non-negative integer and let GG be a connected claw-free graph of order nn. If

σ2k+3(G)≥n−2,\sigma_{2k+3}(G)\geq n-2,

then GG has a spanning tree with at most kk branch vertices. This conjecture proposes a sharper degree-sum condition for spanning trees with boundedly many branch vertices in connected claw-free graphs, improving on earlier sufficient conditions. The supplied text does not state whether the conjecture has been resolved.

References

Primary source

Pham Hoang Ha and Dang Dinh Hanh, “Spanning trees with at most 2 branch vertices in claw - free graphs”, arXiv:1806.00734 (2018).

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.