Published May 23, 2017 | Version v1
Publication Metadata-only

On three parameters of invisibility graphs

Creators

Contributors

Description

The invisibility graph I(X) of a set X ⊆ Rd is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in X . We consider the following three parameters of a set X : the clique number ω(I(X)), the chromatic number χ(I(X)) and the inimum number γ(X) of convex subsets of X that cover X. We settle a conjecture of Matousek and Valtr claiming that for every planar set X, γ(X) can be bounded in terms of χ(I(X)). As a part of the proof we show that a disc with n one-point holes near its boundary has χ(I(X)) ≥ log log(n) but ω(I(X)) = 3. We also find sets X in R5 with χ(I(X)) = 2, but γ(X) arbitrarily large.

Abstract

Czech Science Foundation

Abstract

Ministry of Education, Youth and Sports of the Czech Republic

Abstract

European Science Foundation

Abstract

Országos Tudományos Kutatási Alapprogramok (OTKA)

Abstract

Centre Interfacultaire Bernoulli

Abstract

Swiss National Science Foundation

Additional details

Identifiers

URL
https://idus.us.es/handle/11441/60268
URN
urn:oai:idus.us.es:11441/60268

Origin repository

Origin repository
USE