NP-hardness conjecture for the maximum chromatic crossing number

About 2 years old · traced to

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.

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.