On Colourability of Polygon Visibility Graphs

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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	https://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