On Colourability of Polygon Visibility Graphs

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	CAGIRICI Onur HLINĚNÝ Petr ROY Bodhayan
Year of publication	2018
Type	Article in Proceedings
Conference	37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
MU Faculty or unit	Faculty of Informatics
Citation
Doi	http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.21
Field	Informatics
Keywords	polygon visibility graph; graph coloring; NP-completeness
Description	We study the problem of colouring the visibility graphs of polygons. In particular, we provide a polynomial algorithm for 4-colouring of the polygon visibility graphs, and prove that the 6-colourability question is already NP-complete for them.
Related projects:	Structural properties, parameterized tractability and hardness in combinatorial problems Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VI. Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity Rozsáhlé výpočetní systémy: modely, aplikace a verifikace VII.