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

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Independence Number of Intersection Graphs of Axis-Parallel Segments

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/21.11116/0000-000C-1F1D-3 Version Permalink: https://hdl.handle.net/21.11116/0000-000E-2281-9
Genre: Paper

Files

show Files
hide Files
:
arXiv:2205.15189.pdf (Preprint), 775KB
View   Save
File Permalink:
https://hdl.handle.net/21.11116/0000-000C-1F1F-1
Name:
arXiv:2205.15189.pdf
Description:
File downloaded from arXiv at 2023-01-04 11:46
OA-Status:
Green
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Locators

show

Creators

show
hide
 Creators:
Caoduro, Marco1, Author
Cslovjecsek, Jana1, Author
Pilipczuk, Michał1, Author
Węgrzycki, Karol2, Author                 
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

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

Details

show
hide
Language(s): eng - English
 Dates: 2022-05-302022
 Publication Status: Published online
 Pages: 10 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2205.15189
BibTex Citekey: Caoduro2205.15189
URI: https://arxiv.org/abs/2205.15189
 Degree: -

Event

show

Legal Case

show

Project information

show hide
Project name : BOBR
Grant ID : 948057
Funding program : Horizon 2020 (H2020)
Funding organization : European Commission (EC)
Project name : TIPEA
Grant ID : 850979
Funding program : Horizon 2020 (H2020)
Funding organization : European Commission (EC)

Source

show