On Colourability of Polygon Visibility Graphs
classification
🧮 math.CO
cs.DM
keywords
graphsvisibilitycolourabilitypolygonscolouringnp-completeprovequestion
read the original abstract
We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and prove that the 5-colourability question is already NP-complete for them. For visibility graphs of polygons with holes, we prove that the 4-colourability question is NP-complete.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.