Random planar bipartite-coloring approximation conjecture

From papers

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.

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

No solutions have been posted yet.