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.


Published in:
Journal Of Combinatorial Theory Series B, 105, 6-10
Year:
2014
Publisher:
San Diego, Academic Press Inc Elsevier Science
ISSN:
0095-8956
Keywords:
Laboratories:




 Record created 2014-05-26, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)