Abstrakt
The invisibility graph I(X) of a set X in R^d 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 omega(I(X)), the chromatic number chi(I(X)) and the convexity number gamma(X), which is the minimum number of convex subsets of X that cover X.
We settle a conjecture of Matoušek and Valtr claiming that for every planar set X, gamma(X) can be bounded in terms of chi(I(X)). As a part of the proof we show that a disc with n one-point holes near its boundary has chi(I(X)) >= log log(n) but omega(I(X))=3.
We also find sets X in R^5 with chi(X)=2, but gamma(X) arbitrarily large.