On colouring point visibility graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00118580" target="_blank" >RIV/00216224:14330/20:00118580 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.dam.2019.01.018" target="_blank" >https://doi.org/10.1016/j.dam.2019.01.018</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2019.01.018" target="_blank" >10.1016/j.dam.2019.01.018</a>

Result language

angličtina

Original language name

On colouring point visibility graphs

Original language description

In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. We show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4. (C) 2019 Elsevier B.V. All rights reserved.

Czech name

—

Czech description

—

Type

J_imp - 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

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2020

Confidentiality

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

Name of the periodical

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Volume of the periodical

286

Issue of the periodical within the volume

Nov

Country of publishing house

CH - SWITZERLAND

Number of pages

13

Pages from-to

78-90

UT code for WoS article

000569143200009

EID of the result in the Scopus database

2-s2.0-85061710021