Random planar bipartite-coloring approximation conjecture

About 2 years old · traced to

Let PnP_n consist of nn independent random points uniformly distributed in [0,1]2[0,1]^2, and let a bipartite coloring of PnP_n be any coloring induced by a Euclidean minimum spanning tree. Random bipartite-coloring approximation conjecture. The maximum EMST-ratio is less than 1.11.1 times any bipartite EMST-ratio of the point set with probability tending to 11 as nn goes to infinity.

Computational experiments reported in the source found that the maximum EMST-ratio was at most 1.31.3 times, and rarely more than 1.11.1 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

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.