On Colourability of Polygon Visibility Graphs

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	CAGIRICI Onur HLINĚNÝ Petr ROY Bodhayan
Rok publikování	2024
Druh	Článek v odborném periodiku
Časopis / Zdroj	EUROPEAN JOURNAL OF COMBINATORICS
Fakulta / Pracoviště MU	Fakulta informatiky
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:	Structure of tractable instances of hard algorithmic problems on graphs