Triangle-free intersection graphs of line segments with large chromatic number
classification
🧮 math.CO
cs.CGcs.DM
keywords
numberchromaticgraphslinesegmentsboundedcliquefunction
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.