Staircase characterization conjecture for extremal star-forest decompositions

Let kk be a positive integer, and let GG be a complete geometric graph on 2k2k points. A kk-staircase is the point-set construction defined earlier in the source. Staircase characterization conjecture. If GG admits a decomposition into k+1k+1 plane star-forests and the convex hull of V(G)V(G) has size k+1k+1, then V(G)V(G) can be described as a kk-staircase. The source reports that computations on point sets with 66 and 88 points found no counterexamples, but gives no proof or resolution. Thus the characterization remains open.

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).

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.