On Three Parameters of Invisibility Graphs

摘要

The invisibility graph I(X) of a set X C 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.