Bipartite-coloring approximation conjecture for planar MAX-EMST-ratio
Let be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of and partitioning so that every edge of the chosen tree has endpoints of different colors. Bipartite-coloring approximation conjecture. For every point set in , the EMST-ratio for any bipartite coloring is a -approximation for the maximum EMST-ratio.
The source presents triangular chains as examples whose approximation proportion approaches , and notes that proving this conjecture would yield an -time -approximation algorithm for the planar problem.
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.