On Colourability of Polygon Visibility Graphs
| Autoři | |
|---|---|
| Rok publikování | 2024 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | EUROPEAN JOURNAL OF COMBINATORICS |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | arXiv preprint |
| Doi | http://dx.doi.org/10.1016/j.ejc.2023.103820 |
| Klíčová slova | polygon visibility graph; graph coloring; NP-completeness |
| Popis | 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. |
| Související projekty: |