




















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 $α\ge n/4 + Ω(\sqrt{n})$. We complement this with a construction of a graph in this class satisfying $α\le n/4 + c \sqrt{n}$ for an absolute constant $c$, which demonstrates the optimality of our result.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。