Nordhaus–Gaddum conjecture for independent position chromatic numbers

About 1 year old · traced to

Let GG be a graph of order nn, let G‾\overline{G} be its complement, and choose π∈{gp⁡,mp⁡}\pi\in\{\operatorname{gp},\operatorname{mp}\}, where gp⁡\operatorname{gp} and mp⁡\operatorname{mp} denote general and monophonic position, respectively. Let χπi(G)\chi_{\pi_{\rm i}}(G) denote the chromatic number whose color classes are independent π\pi-position sets. Nordhaus–Gaddum conjecture.

χπi(G)+χπi(G‾)≤n+1.\chi_{\pi_{\rm i}}(G)+\chi_{\pi_{\rm i}}(\overline{G})\leq n+1.

The survey identifies this as an open problem; no general proof or counterexample is reported.

References

Primary source

Ullas Chandran S. V., Sandi Klavžar and James Tuite, “The General Position Problem: A Survey”, arXiv:2501.19385 (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.