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