# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Independence Number of Intersection Graphs of Axis-Parallel Segments

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2205.15189.pdf

(Preprint), 775KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Caoduro, M., Cslovjecsek, J., Pilipczuk, M., & Węgrzycki, K. (2022). Independence Number of Intersection Graphs of Axis-Parallel Segments. Retrieved from https://arxiv.org/abs/2205.15189.

Cite as: https://hdl.handle.net/21.11116/0000-000C-1F1D-3

##### 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.

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.