Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane

2018/02/27 by Mütze, Torsten, Walczak, Bartosz, Wiechert, Veit
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1802.09969

Abstract

It is shown that shift graphs can be realized as disjointness graphs of 1-intersecting curves in the plane. This implies that the latter class of graphs is not χ-bounded.

Related

• The Generalised Shift Graph
• Coloring curves that cross a fixed curve
• Outerstring graphs are χ-bounded
• Coloring Hasse diagrams and disjointness graphs of curves
• On the Resolution Graph of a Plane Curve