Bipartite-coloring approximation conjecture for planar MAX-EMST-ratio

From papers

Let PR2P\subseteq\mathbb{R}^2 be a finite point set. A bipartite coloring is obtained by choosing a Euclidean minimum spanning tree of PP and partitioning P=RBP=R\cup B so that every edge of the chosen tree has endpoints of different colors. Bipartite-coloring approximation conjecture. For every point set in R2\mathbb{R}^2, the EMST-ratio for any bipartite coloring is a (1.5)(1.5)-approximation for the maximum EMST-ratio.

The source presents triangular chains as examples whose approximation proportion approaches 1.51.5, and notes that proving this conjecture would yield an O(nlogn)O(n\log n)-time (1.5)(1.5)-approximation algorithm for the planar problem.

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.