Informace o publikaci

On Colourability of Polygon Visibility Graphs

Autoři

CAGIRICI Onur HLINĚNÝ Petr ROY Bodhayan

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: