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í	2018
Druh	Článek ve sborníku
Konference	37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Doi	http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.21
Obor	Informatika
Klíčová slova	polygon visibility graph; graph coloring; NP-completeness
Popis	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.
Související projekty:	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.