Triangle-free families of segments with large chromatic number

Series: 
Graph Theory Seminar
Thursday, February 16, 2012 - 12:05
1 hour (actually 50 minutes)
Location: 
Skiles 006
,  
Jagiellonian University, Krakow, Poland
Organizer: 
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.