On Colourability of Polygon Visibility Graphs
| Authors | |
|---|---|
| Year of publication | 2024 |
| Type | Article in Periodical |
| Magazine / Source | EUROPEAN JOURNAL OF COMBINATORICS |
| MU Faculty or unit | |
| Citation | |
| web | arXiv preprint |
| Doi | http://dx.doi.org/10.1016/j.ejc.2023.103820 |
| Keywords | polygon visibility graph; graph coloring; NP-completeness |
| Description | 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. |
| Related projects: |