Independence number of intersection graphs of axis-parallel segments

05/30/2022
by   Marco Caoduro, et al.
0

We prove that for any triangle-free intersection graph of n axis-parallel segments in the plane, the independence number α of this graph is at least α≥ n/4 + Ω(√(n)). We complement this with a construction of a graph in this class satisfying α≤ n/4 + c √(n) for an absolute constant c, which demonstrates the optimality of our result.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset