Informace o publikaci
On Colourability of Polygon Visibility Graphs
Autoři | |
---|---|
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 | |
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: |