The $$\chi $$-Binding Function of d-Directional Segment Graphs
Lech Duraj, Ross J. Kang, Hoang La, Jonathan Narboni, Filip Pokrývka, Clément Rambaud, Amadeus Reinald · Discrete & Computational Geometry · 2025
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$$ 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)$$ χ ( G ) of G is at most $$d\omega $$ d ω . 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 $$ ω ↦ d ω for $$\omega $$ ω even and $$\omega \mapsto d(\omega -1)+1$$ ω ↦ d ( ω - 1 ) + 1 for $$\omega $$ ω odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $$d=2$$ d = 2 .