Random planar bipartite-coloring approximation conjecture
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.
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
Afrouz Jabal Ameli, Faezeh Motiei and Morteza Saghafian, “On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum”, arXiv:2409.11079 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.