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

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro