Article ID Journal Published Year Pages File Type
4656876 Journal of Combinatorial Theory, Series B 2014 5 Pages PDF
Abstract

In the 1970s Erdős 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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , , , ,