pith. sign in

arxiv: 1209.1595 · v5 · pith:ODRPNAWGnew · submitted 2012-09-07 · 🧮 math.CO · cs.CG· cs.DM

Triangle-free intersection graphs of line segments with large chromatic number

classification 🧮 math.CO cs.CGcs.DM
keywords numberchromaticgraphslinesegmentsboundedcliquefunction
0
0 comments X
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.