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