The $$\chi $$-Binding Function of d-Directional Segment Graphs

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