文章基本信息

标题：On Colourability of Polygon Visibility Graphs
作者：Onur Cagirici ; Petr Hlinen{\'y ; Bodhayan Roy 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：93
页码：21:1-21:14
DOI：10.4230/LIPIcs.FSTTCS.2017.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：polygon visibility graph; graph coloring; NP-completeness