Connected transversal threshold conjecture for complete multipartite graphs

Let r4r\geq 4, let KrK_r be the complete graph on rr parts, and let Tr\mathcal{T}_r denote the family of all trees on rr vertices. For an rr-partite graph, write πKr(Tr)\pi_{K_r}(\mathcal{T}_r) for the smallest rr-partite density forcing a connected transversal tree.

Connected transversal conjecture. The lower bound in Theorem~ is tight. In particular, for any r4r\geq 4, every rr-partite graph with rr-partite density at least 352\frac{3-\sqrt{5}}{2} contains a transversal tree on rr vertices.

The conjecture would determine the connected-transversal density threshold for complete multipartite graphs, improving the presently established bounds.

Sources & referencesView supporting material

Primary source

Leila Badakhshian, Victor Falgas-Ravry and Maryam Sharifzadeh, “On density conditions for transversal trees in multipartite graphs”, arXiv:2305.05713 (2023).

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.