On Colourability of Polygon Visibility Graphs
Onur Çağırıcı, Petr Hliněný, Bodhayan Roy · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
We study the problem of colouring the visibility graphs of polygons. In particular, we provide a polynomial algorithm for 4-colouring of the polygon visibility graphs, and prove that the 6- colourability question is already NP-complete for them.