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

arrow_drop_up

Comments

Sign up or login to leave a comment