Connected transversal threshold conjecture for complete multipartite graphs
Connected transversal threshold conjecture for complete multipartite graphs
Let , let be the complete graph on parts, and let denote the family of all trees on vertices. For an -partite graph, write for the smallest -partite density forcing a connected transversal tree.
Connected transversal conjecture. The lower bound in Theorem~ is tight. In particular, for any , every -partite graph with -partite density at least contains a transversal tree on 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.