On Colourability of Polygon Visibility Graphs
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Colourability of Polygon Visibility Graphs
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
On Colourability of Polygon Visibility Graphs
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA20-04567S" target="_blank" >GA20-04567S: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2024
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
EUROPEAN JOURNAL OF COMBINATORICS
ISSN
0195-6698
e-ISSN
1095-9971
Svazek periodika
117
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
13
Strana od-do
103820
Kód UT WoS článku
001161332700001
EID výsledku v databázi Scopus
2-s2.0-85171637228