English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Independence Number of Intersection Graphs of Axis-Parallel Segments

MPS-Authors
/persons/resource/persons252863

Węgrzycki,  Karol       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.