Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS
 
research article

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Caoduro, Marco
•
Cslovjecsek, Jana Tabea  
•
Pilipczuk, Michal
Show more
January 1, 2023
Journal Of Computational Geometry

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying alpha <= n/4 + c root n for an absolute positive constant c, which demonstrates the optimality of our result.Wegner's conjecture states that the clique covering number of the intersection graph of axis-parallel rectangles can be bounded by twice its independence number. As a consequence of our results, we show that the multiplicative constant in Wegner's conjecture is tight already for the highly restricted case of axis-parallel segments, even with the assumption of triangle-freeness. Still, for this class, we improve on Wegner's bound by an additive term of order root alpha.

  • Details
  • Metrics
Type
research article
DOI
10.20382/jocg.v14i1a5
Web of Science ID

WOS:001091468700001

Author(s)
Caoduro, Marco
Cslovjecsek, Jana Tabea  
Pilipczuk, Michal
Wegrzycki, Karol
Date Issued

2023-01-01

Publisher

Carleton Univ, Dept Mathematics & Statistics

Published in
Journal Of Computational Geometry
Volume

14

Issue

1

Start page

144

End page

156

Subjects

Physical Sciences

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
FunderGrant Number

European Research Council (ERC) under the European Union

948057

Available on Infoscience
February 19, 2024
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/204093
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés