Abstract

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying alpha <= n/4 + c root n for an absolute positive constant c, which demonstrates the optimality of our result.Wegner's conjecture states that the clique covering number of the intersection graph of axis-parallel rectangles can be bounded by twice its independence number. As a consequence of our results, we show that the multiplicative constant in Wegner's conjecture is tight already for the highly restricted case of axis-parallel segments, even with the assumption of triangle-freeness. Still, for this class, we improve on Wegner's bound by an additive term of order root alpha.

Details