On Colourability of Polygon Visibility Graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00139104" target="_blank" >RIV/00216224:14330/24:00139104 - isvavai.cz</a>
Result on the web
<a href="http://arxiv.org/abs/1906.01904" target="_blank" >http://arxiv.org/abs/1906.01904</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ejc.2023.103820" target="_blank" >10.1016/j.ejc.2023.103820</a>

Result language
angličtina
Original language name
On Colourability of Polygon Visibility Graphs
Original language description
We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and prove that the 5-colourability question is already NP-complete for them. For visibility graphs of polygons with holes, we prove that the 4-colourability question is NP-complete.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)