Nordhaus–Gaddum conjecture for independent position chromatic numbers

From papers

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.

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

Ullas Chandran S. V., Sandi Klavžar and James Tuite, “The General Position Problem: A Survey”, arXiv:2501.19385 (2026).

Solutions 0

No solutions have been posted yet.