The χ-Binding Function of d-Directional Segment Graphs

Given a positive integer d, the class d-DIR is defined as all those intersection graphs formed from a finite collection of line segments in R2 having at most d slopes. Since each slope induces an interval graph, it easily follows for every G in d-DIR with clique number at most ω that the chromatic number χ(G) of G is at most dω. We show for every even value of ω how to construct a graph in d-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the χ-binding function of d-DIR is ω↦dω for ω even and ω↦d(ω-1)+1 for ω odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case d = 2.