论文标题
轴平行段的交叉图的独立数
Independence number of intersection graphs of axis-parallel segments
论文作者
论文摘要
我们证明，对于平面中$ n $ axis-并行段的任何无三角形的相交图，该图的独立性$α$至少为$α\ ge n/4 +ω（\ sqrt {n}）$。我们通过在此类中的图形结构进行补充，以满足绝对常数$ c $的$α\ le n/4 + c \ sqrt {n} $，这证明了我们结果的最佳性。
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.
