The NP-hardness conjecture for lower oriented general position number two

Less than 1 year old · traced to

Let GG be a graph, and let gp→(G){\rm gp}_{\rightarrow}(G) denote the minimum general position number over all orientations of GG. The lower-number-two hardness conjecture. It is NP-hard to decide whether

gp→(G)=2.{\rm gp}_{\rightarrow}(G)=2.

The supplied text does not provide a proof or resolution, so the complexity of this decision problem remains open.

References

Primary source

Ullas Chandran S. V., Gabriele Di Stefano, Grahame Erskine, Haritha S, Elias John Thomas and James Tuite, “The general position number of digraphs”, arXiv:2604.15909 (2026).

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.