The invisibility graph I(X) of a set X (is contained 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 settle a conjecture of Matousek and Valtr claiming that for invisibility graphs of planar sets, the chromatic number cannot be bounded in terms of the clique number.
展开▼
