Loading...
research article
Triangle-free intersection graphs of line segments with large chromatic number
In the 1970s Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k we construct a triangle-free family of line segments in the plane with chromatic number greater than k. Our construction disproves a conjecture of Scott that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number. (C) 2013 Elsevier Inc. All rights reserved.
Type
research article
Web of Science ID
WOS:000334975800002
Authors
Pawlik, Arkadiusz
•
Kozik, Jakub
•
Krawczyk, Tomasz
•
•
Micek, Piotr
•
Trotter, William T.
•
Publication date
2014
Publisher
Published in
Volume
105
Start page
6
End page
10
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
May 26, 2014
Use this identifier to reference this record