Lower-bound conjecture for plane star-forest decompositions of complete geometric graphs
Lower-bound conjecture for plane star-forest decompositions of complete geometric graphs
A complete geometric graph is a complete graph drawn with vertices in general position and straight-line edges. A plane star-forest is a forest whose connected components are stars. Star-forest decomposition lower-bound conjecture. Let . There is no complete geometric graph with vertices that can be decomposed into fewer than
plane star-forests. The source presents this as a conjecture based on the lower bound known for vertices in convex position; its general case remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Todor Antić, Jelena Glišić and Milan Milivojčević, “Star-Forest Decompositions of Complete Graphs”, arXiv:2402.11044 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.