On Colourability of Polygon Visibility Graphs

• 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
• 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.