Random planar bipartite-coloring approximation conjecture
Let consist of independent random points uniformly distributed in , and let a bipartite coloring of be any coloring induced by a Euclidean minimum spanning tree. Random bipartite-coloring approximation conjecture. The maximum EMST-ratio is less than times any bipartite EMST-ratio of the point set with probability tending to as goes to infinity.
Computational experiments reported in the source found that the maximum EMST-ratio was at most times, and rarely more than times, the computed bipartite EMST-ratio for the tested random point sets. The asymptotic claim remains open.
References
Primary source
Afrouz Jabal Ameli, Faezeh Motiei and Morteza Saghafian, “On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum”, arXiv:2409.11079 (2025).
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
No solutions have been posted yet.