Triangle-free geometric intersection graphs with no large independent sets

2014/04/30 by Bartosz Walczak · 1 citation
Mathematics · Computer Science · #math.CO #cs.CG #cs.DM #math.MG #msc:05C62 #msc:05C15

paper · pdf · doi:10.1007/s00454-014-9645-y

published as Discrete Comput.Geom. 53 (2015) 221-225 · Change of the title, minor revision

arxiv created 2014/12/26 · arxiv updated 2014/12/30

Abstract

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.

Cited by

• On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs