NP-completeness of mutual-visibility coloring
A graph has a mutual-visibility coloring if its vertices can be colored so that the required mutual-visibility condition holds; the associated decision problem asks whether admits such a coloring with a prescribed number of colors.
Mutual-visibility coloring conjecture. The mutual-visibility coloring decision problem is NP-complete.
The paper proves NP-completeness for the independent version, even for graphs with universal vertices, and conjectures that the same computational complexity holds for the basic version.
References
- Boštjan Brešar, Iztok Peterin, Babak Samadi and Ismael G. Yero, “Independent mutual-visibility coloring and related concepts”, arXiv:2505.04144 (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.