Triangle-free geometric intersection graphs with no large independent sets

Bartosz Walczak

It is proved that there are triangle-free intersection graphs of line segments in the plane with arbitrarily small ratio between the maximum size of an independent set and the total number of vertices.

Knowledge Graph



Sign up or login to leave a comment