The $\chi$-binding function of $d$-directional segment graphs

Abstract

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 ${\mathbb{R}}^2$ 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 $\omega$ that the chromatic number $\chi (G)$ of $G$ is at most $d\omega$. We show for every even value of $\omega$ 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 $\chi$-binding function of $d$-DIR is $\omega \mapsto d\omega$ for $\omega$ even and $\omega \mapsto d(\omega -1)+1$ for $\omega$ odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $d=2$.

11 pages, 3 figures; v2 includes corrections for referee comments