2016/10/04 by Ajit A. Diwan, Diwan, Ajit Arvind, Bodhayan Roy +1
Computer Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1610.00952
In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. We show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.