NP-hardness conjecture for the maximum chromatic crossing number

From papers

For a finite point set in the plane and a red-blue partition, the chromatic crossing number is the number of crossings between an edge of EMST(R)\operatorname{EMST}(R) and an edge of EMST(B)\operatorname{EMST}(B). The maximum chromatic crossing number is the largest such number over all colorings. Maximum chromatic crossing-number conjecture. Finding the maximum chromatic crossing number of a point set in the plane is NP-hard.

The source poses this as a complexity question alongside questions about the possible size of the parameter and its relation to the EMST-ratio; no resolution is given.

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.