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

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.

Small corrections, bibliography update

References in corpus (1)

• Triangle-free geometric intersection graphs with large chromatic number

Cited by in corpus (12)

• Coloring triangle-free rectangle overlap graphs with $O(\log \log n)$ colors
• Cops and Robbers on Intersection Graphs
• Treewidth versus clique number. I. Graph classes with a forbidden structure
• On-line approach to off-line coloring problems on graphs with geometric representations
• Coloring intersection graphs of arc-connected sets in the plane
• Triangle-free geometric intersection graphs with no large independent sets
• Triangle-free graphs that do not contain an induced subdivision of $K_4$ are 3-colorable
• Burling graphs revisited, part I: New characterizations
• Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
• Decomposition of multiple packings with subquadratic union complexity
• Burling graphs revisited, part III: Applications to $\chi$-boundedness
• Coloring lines and Delaunay graphs with respect to boxes