Triangle-free families of segments with large chromatic number

Graph Theory Seminar
Thursday, February 16, 2012 - 12:05pm
1 hour (actually 50 minutes)
Skiles 006
Jagiellonian University, Krakow, Poland
We consider intersection graphs of families of straight line segments in the euclidean plane and show that for every integer k, there is a family S of line segments so that the intersection graph G of the family S is triangle-free and has chromatic number at least k. This result settles a conjecture of Erdos and has a number of applications to other classes of intersection graphs.