hide
Free keywords:
Mathematics, Combinatorics, math.CO,Computer Science, Computational Geometry, cs.CG,Computer Science, Discrete Mathematics, cs.DM,
Abstract:
We prove that for any triangle-free intersection graph of $n$ axis-parallel
segments in the plane, the independence number $\alpha$ of this graph is at
least $\alpha \ge n/4 + \Omega(\sqrt{n})$. We complement this with a
construction of a graph in this class satisfying $\alpha \le n/4 + c \sqrt{n}$
for an absolute constant $c$, which demonstrates the optimality of our result.
