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

Lech Duraj Theoretical Computer Science Department, Faculty of Mathematics and
Computer Science, Jagiellonian University, Kraków, Poland. Partially supported
by National Science Center of Poland grant 2019/34/E/ST6/00443.  Ross J. Kang
Korteweg–de Vries Institute for Mathematics, University of Amsterdam,
Netherlands. Partially supported by a Vidi grant (639.032.614) and the
Gravitation Programme NETWORKS (024.002.003) of the Dutch Research Council
(NWO<EMAIL_ADDRESS>Hoang La Theoretical Computer Science Department,
Jagiellonian University, Kraków, Poland. Partially supported by a Polish
National Science Center grant BEETHOVEN; UMO-2018/31/G/ST1/03718.
<EMAIL_ADDRESS>Jonathan Narboni11footnotemark: 1 Filip Pokrývka
Faculty of Informatics, Masaryk University, Brno, Czech Republic.
<EMAIL_ADDRESS>Clément Rambaud DIENS, École Normale Supérieure, CNRS, PSL
University, Paris, France<EMAIL_ADDRESS>Amadeus Reinald LIRMM,
CNRS, Université de Montpellier, France. Supported by the ANR project DIGRAPHS
(ANR-19-CE48-0013<EMAIL_ADDRESS>
###### 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 refutes said
conjecture of Bhattacharya, Dvořák and Noorizadeh.

##  1 Introduction

In structural graph theory, a fundamental task is to characterise the complex,
global parameter of chromatic number $\chi$ in terms of the simpler, more
local parameter of clique number $\omega$. For a given graph class, the
question of whether this task is even well-defined belongs to the theory of
$\chi$-boundedness, an area systematically initiated by Gyárfás in the 1980s
[Gyá87]. A graph class $\mathcal{G}$ is called $\chi$-bounded if there is some
function $f_{\mathcal{G}}$ such that $\chi(G)\leq f_{\mathcal{G}}(\omega(G))$
for any $G\in\mathcal{G}$, and, if that is so, the optimal choice of
$f_{\mathcal{G}}$ is called the $\chi$-binding function of $\mathcal{G}$. Note
that the triangle-free graphs of arbitrarily large chromatic number give rise
to many interesting graph classes that are not $\chi$-bounded. This area of
mathematics is deep and active, but despite many recent advances, there are
many important classes for which the question of $\chi$-boundedness is
difficult and remains open; for a nice recent account of the state of the art,
see [SS20]. Suffice it to say that determination of the $\chi$-binding
function for a nontrivial (non-perfect) class is generally considered a
rarity.

Since even before the beginning [AG60], much attention has been focused on
intersection classes, that is, graph classes defined by taking some natural
collection of sets, usually geometrically-defined, and forming for every
finite subcollection of those sets an auxiliary graph in which each vertex
corresponds to a set, and two vertices are connected by an edge if and only if
the corresponding sets have a nontrivial intersection. Such a restriction is
not too confining, not only because many intersection classes are fundamental
to the structural understanding of graphs (consult, e.g. [MM99, Spi03] for
more context), but also because intersection classes are more than rich enough
for its $\chi$-boundedness theory to contain many fascinating challenges.

As one prominent (and pertinent) example, consider the collection of straight
line segments in the plane $\mathbb{R}^{2}$ (or more formally, the collection
of those closed intervals drawn between some pairs of points in
$\mathbb{R}^{2}$). Its intersection class is called the segment (intersection)
graphs. If all the segments happen to lie in parallel, then the resulting
segment graph is an interval graph, and thus perfect; that is, it has equality
between $\chi$ and $\omega$. One should not expect this to remain true when we
allow the segment slopes to vary, but it is reasonable to ask if there might
remain a good relationship between $\chi$ and $\omega$, that is, are segment
graphs $\chi$-bounded? Indeed, Erdős asked this in the 1970s (see [Gyá87,
PKK+14] for more details of the problem’s provenance).

Despite sustained attention and nice partial results (see e.g. [KN95, McG00,
Suk14]), Erdős’s innocent-looking but very difficult challenge was not
resolved until 2014, and in the negative. Work of Pawlik, Kozik, Krawczyk,
Lasoń, Micek, Trotter, and Walczak [PKK+14] provided a strikingly elegant
construction of triangle-free segment graphs of arbitrarily large chromatic
number. Interestingly, the graphs produced by the construction are isomorphic
to the intersection graphs that were exhibited by Burling [Bur65] to show that
the intersection class for axis-aligned boxes in ${\mathbb{R}}^{3}$ is not
$\chi$-bounded.

One might consider this a coda, but permit us to prolong the narrative, in
particular by parameterising according to the number of segment slopes. We
first note that the construction of Pawlik et al. must have arbitrarily many
slopes. Suppose to the contrary that the segments admit at most $d$ slopes. By
the same observation as above, each slope induces a perfect graph $H$ having
$\chi(H)$ equal to $\omega(H)\leq 2$. By colouring the slopes disjointly from
one another, we can conclude that $\chi$ is at most $2d$ for the entire graph,
a contradiction.

More generally, given a positive integer $d$, we refer to the $d$-directional
segment graphs as those intersection graphs formed from a collection of line
segments in $\mathbb{R}^{2}$ having at most $d$ distinct slopes. Call the
class of such graphs $d$-DIR. (Take note of the subtlety that this is not per
se an intersection class, but rather a union of many of them.) What we just
argued is that $\chi(G)\leq d\omega(G)$ for any $G$ in $d$-DIR. Thus, in a
simple fashion, we can conclude that the graph class $d$-DIR is
$\chi$-bounded.

The question we would like to address here is, what is the $\chi$-binding
function of $d$-DIR? This question was raised recently by Bhattacharya, Dvořák
and Noorizadeh [BDN23]. They proved that there are $2$-directional segment
graphs of clique number $2t$ and chromatic number $4t$, for all
$t\in\mathbb{N}$, which attains the bound of the above simple argument in this
special case. They moreover conjectured that that simple bound is optimal in
general, that is, that $\omega\mapsto d\omega$ is the $\chi$-binding function
of $d$-DIR.

We succeeded in completely resolving this question as follows.

######  Theorem 1.

The $\chi$-binding function of $d$-DIR is

$\displaystyle\omega\mapsto\begin{cases}d\omega&\text{if $\omega$ is even,
or}\\\ d(\omega-1)+1&\text{if $\omega$ is odd.}\end{cases}$

One can interpret this statement as a graceful generalisation of perfection in
the $d=1$ case.

The crux in Theorem 1 is to prove the lower bound in the even $\omega$ case.
Here is a rough sketch of that construction, which at a high level combines
aspects of both the construction of Pawlik et al. and that of Bhattacharya et
al., and indeed strengthens/refines both constructions. We start by fixing
$\omega=2$ and proceed by induction on $d$, exhibiting graphs achieving high
fractional chromatic number. We refine the induction used by Pawlik et al. by
controlling, at every step, the growth of the number of slopes required for
achieving a given fractional chromatic number. We then obtain the result for
all even $\omega>2$ by blowing up each segment by a factor $\omega/2$,
building on ideas of Bhattacharya et al..

The structure of the paper is as follows. In Section 2, we lay the ground for
our proof by introducing the notions and tools used throughout the paper. Then
we settle the even $\omega$ case in Section 3. The lower bound for the odd
$\omega$ case in Section 4 is a mild adaptation of the even $\omega$
construction. We give a short proof of the upper bound for the odd $\omega$
case in Section 5. We end with some open questions for future research in
Section 6.

##  2 Preliminaries

###  2.1 Fractional colouring

In the proof, we will essentially work with fractional chromatic number, a
standard parameter lower bounding the chromatic number, which has many
equivalent definitions. For all positive integers $a$ and $t$, a _$t$ -fold
$a$-colouring_ of a graph $G$ is a function
$\varphi:V(G)\to\binom{\\{1,\dots,a\\}}{t}$ such that for every edge $uv\in
E(G)$, $\varphi(u)\cap\varphi(v)=\emptyset$. Recall that the fractional
chromatic number $\chi_{f}(G)$ of a graph $G$ is the limit of $a/t$ as
$t\to\infty$ with $a$ being the least integer such that $G$ admits a $t$-fold
$a$-colouring. It holds that $\chi_{f}(G)\leq\chi(G)$ always. For any $t$-fold
colouring $\varphi$ of a graph $G$, if $X$ is a set of vertices of $G$, we
denote by $\varphi(X)$ the set of colours used to colour the vertices in $X$,
i.e. $\varphi(X)=\bigcup_{v\in X}\varphi(v)$.

###  2.2 Segments

A _segment_ $S$ with endpoints $A=(x_{1},y_{1})$ and $B=(x_{2},y_{2})$ in
$\mathbb{R}^{2}$ is the set $\\{A+\lambda(B-A)\mid\lambda\in[0,1]\\}$. The
_length of a segment_ is its Euclidean norm. A _rectangle_ $R$ is defined as
the Cartesian product of two segments $[a,c]\times[b,d]$ with
$a,b,c,d\in\mathbb{R}$ and $c>a$ and $d>b$. A rectangle always has non-zero
area. If the two intervals have the same length, we say that $R$ is a
_square_. We naturally define the _left_ , _right_ , _top_ and _bottom_
_sides_ of a rectangle $R$ as the four segments whose union is the boundary of
$R$. The left and right side of $R$ are the vertical sides of $R$, and the top
and bottom sides of $R$ are the horizontal sides of $R$. The length of a
vertical side is the _height_ of $R$, the length of a horizontal side is the
_width_ of $R$. The aspect ratio of $R$ is the height divided by the width of
$R$. A segment $S$ _crosses a rectangle $R$ vertically or horizontally_ if $S$
intersects the two horizontal or vertical sides of $R$, respectively. We say
that a rectangle $R_{1}$ crosses a rectangle $R_{2}$ vertically (respectively,
horizontally) if the left and right sides (respectively, the top and bottom
sides) of $R_{1}$ cross the rectangle $R_{2}$ vertically (respectively,
horizontally). If $R_{1}$ crosses $R_{2}$ vertically, then $R_{2}$ crosses
$R_{1}$ horizontally. The _slope_ of a segment in $\mathbb{R}^{2}$ with
endpoints $(x_{1},y_{1}),(x_{2},y_{2})$ is $\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$
if $x_{1}\neq x_{2}$, and $\infty$ otherwise. The _slope number_ of a finite
family $\mathcal{S}$ of segments is the cardinality of the set of the slopes
of segments in $\mathcal{S}$.

Given a set $\mathcal{S}$ of segments, the _intersection graph_
$G(\mathcal{S})$ of $\mathcal{S}$ is the graph with vertex set $\mathcal{S}$
and with edges consisting of all pairs $SS^{\prime}$ with
$S,S^{\prime}\in\mathcal{S}$ such that $S\cap S^{\prime}\neq\emptyset$.

A _$t$ -blowup of a segment_ is a multiset of $t$ copies of the same segment.
A _$t$ -blowup of a set of segments_ is the multiset of the $t$-blowup of the
segments. A _$t$ -blowup of a graph_ is the graph obtained from $G$ by
replacing every vertex by a copy of $K_{t}$, and every edge by a copy of
$K_{t,t}$. Observe that a $t$-fold colouring of $G$ corresponds to a colouring
of the $t$-blowup of $G$.

###  2.3 Configurations

We now introduce the notion of probes, first used in [PKK+14]. Let
$\mathcal{S}$ be a family of segments in _the unit square_
$\mathcal{U}=[0,1]\times[0,1]$. Let $P=[a,c]\times[b,d]$ be a rectangle
included in $\mathcal{U}$. We denote by $\mathcal{S}(P)$ the set of segments
in $\mathcal{S}$ intersecting $P$. The _right extension_ of $P$ is the
rectangle $[a,1]\times[b,d]$. The rectangle $P=[a,c]\times[b,d]$ is a _probe_
for $\mathcal{S}$ if the following hold:

  * •

$c=1$, that is, the left side of $P$, lies on the boundary of $\mathcal{U}$;

  * •

all segments in $\mathcal{S}(P)$ cross $P$ vertically; and

  * •

all segments in $\mathcal{S}(P)$ are pairwise disjoint.

Given a probe $P$, a _root_ of $P$ is a rectangle $[a,c^{\prime}]\times[b,d]$
where $c^{\prime}$ is a real number such that $[a,c^{\prime}]\times[b,d]$ is
disjoint from every segment in $\mathcal{S}$.

A _configuration_ is a pair $\mathcal{C}=(\mathcal{S},\mathcal{P})$ with
$\mathcal{S}$ a set of segments in $\mathcal{U}$ and $\mathcal{P}$ a family of
probes for $\mathcal{S}$.

For convenience, we define the intersection graph $G(\mathcal{C})$ of a
configuration $\mathcal{C}=(\mathcal{S},\mathcal{P})$ as $G(\mathcal{S})$. We
say that $\mathcal{C}$ is triangle-free if $G(\mathcal{S})$ is a triangle-free
graph.

Let $R$ be a square inside $\mathcal{U}$ and let $\psi$ be the positive
homothety mapping $\mathcal{U}$ to $R$. The $R$-scaled copy of $\mathcal{C}$
is the configuration
$\mathcal{C}^{\prime}=(\mathcal{S}^{\prime},\mathcal{P}^{\prime})$ where
$\mathcal{S}^{\prime}$ is the set of images of the segments in $\mathcal{S}$
by $\psi$ and $\mathcal{P}^{\prime}$ is the set of the right-extensions of the
images by $\psi$ of the probes in $\mathcal{P}$. Observe that
$\mathcal{S}^{\prime}$ has the same set of slopes as $\mathcal{S}$.

###  2.4 Copying configurations

Our refinement on the construction of [PKK+14] is obtained at the cost of
adding significantly many more copies of the construction achieving $\chi$
colours when building the graph requiring $\chi+1$ colours. Here, we describe
this operation. For every configuration $\mathcal{C}$ and for every positive
integer $k$, we define the new configuration $\mathcal{C}^{(k)}$ with segments
set $\mathcal{S}^{(k)}$ and probes set $\mathcal{P}^{(k)}$ as “a way of
joining $k$ independent copies of $\mathcal{C}$ together”. With every probe
$P\in\mathcal{P}^{(k)}$, we associate a set of $k$ sub-rectangles of $P$ that
we call the _pillars_ of $P$. The pillars have the same height as $P$, are
pairwise disjoint, and no pillars start from the left side of $P$ so that
there is a root of $P$ not belonging to any pillar. Informally, each pillar
will correspond to a copy of $\mathcal{C}$.

Formally, $\mathcal{C}^{(k)}=(\mathcal{S}^{(k)},\mathcal{P}^{(k)})$ is defined
as follows:

  * •

If $k=1$, then $\mathcal{C}^{(1)}=\mathcal{C}$. For every probe $P$, we define
its only pillar $I_{0}^{P}$ as the minimal rectangle containing $P$ minus a
root. Every segment of $\mathcal{S}(P)$ is a segment of
$\mathcal{S}(I_{0}^{P})$ and it also crosses $I_{0}^{P}$ vertically.

  * •

If $k\geq 2$, then for every probe $P\in\mathcal{P}^{(k-1)}$ we choose a
square $R_{P}$ in a root of $P$ disjoint from its pillars and insert an
$R_{P}$-scaled copy $\mathcal{C}_{P}=(\mathcal{S}_{P},\mathcal{P}_{P})$ of
$\mathcal{C}$. We define
$\mathcal{S}^{(k)}=\mathcal{S}^{(k-1)}\cup\bigcup_{P\in\mathcal{P}^{(k-1)}}\mathcal{S}_{P}$
and $\mathcal{P}^{(k)}=\bigcup_{P\in\mathcal{P}^{(k-1)}}\mathcal{P}_{P}$. In
other words, instead of $P$, we take new probes, generated in $R_{P}$ by the
new copy of $\mathcal{C}$, extended to the right. These new probes are then
wholly contained in $P$.

For every such probe $P^{\prime}$, we define $k$ different pillars of
$P^{\prime}$. There are $k-1$ pillars
$I_{0}^{P^{\prime}},I_{1}^{P^{\prime}},\dots,I_{k-2}^{P^{\prime}}$ which are
intersections between the pairwise disjoint pillars
$I_{0}^{P},I_{1}^{P},\dots,I_{k-2}^{P}$ of $P$ and $P^{\prime}$ and one pillar
$I_{k-1}^{P^{\prime}}$ that is the minimal rectangle containing $R_{P}\cap
P^{\prime}$ minus a root of $P^{\prime}$. Since $R_{P}$ is contained in a root
of $P$, $I_{k-1}^{P^{\prime}}$ is also disjoint from
$I_{0}^{P^{\prime}},\dots,I_{k-2}^{P^{\prime}}$. Furthermore, for every
$i\in\\{0,\dots,k-2\\}$, since segments in $\mathcal{S}^{(k-1)}(I_{i}^{P})$
cross $I_{i}^{P}$ vertically, they also cross $I_{i}^{P^{\prime}}$ vertically.
Therefore,
$\mathcal{S}^{(k-1)}(I_{i}^{P})\subseteq\mathcal{S}^{(k)}(I_{i}^{P^{\prime}})$.

Note that $G(\mathcal{C}^{(k)})$ is the union of disjoint copies of
$G(\mathcal{C})$, and in particular $\mathcal{C}^{(k)}$ is triangle-free if
$\mathcal{C}$ is triangle-free. See Figure 1.

Figure 1: Building $\mathcal{C}^{(2)}$ from $\mathcal{C}^{(1)}=\mathcal{C}$.

######  Lemma 2.

Let $\mathcal{C}=(\mathcal{S},\mathcal{P})$ be a configuration and let $t$ be
a positive integer. If there exists a nonnegative integer $s$ such that, for
every $t$-fold colouring $\varphi$ of $G(\mathcal{C})$, there exists a probe
$P\in\mathcal{P}$ such that $|\varphi(\mathcal{S}(P))|\geq s$, then, for every
$t$-fold colouring $\varphi$ of $G(\mathcal{C}^{(k)})$, there exists a probe
$P^{\prime}$ such that, for every pillar $I$ of $P^{\prime}$,
$|\varphi(\mathcal{S}(I))|\geq s$.

###### Proof.

The proof is an induction on $k$.

Suppose that $k=1$. Observe that $\mathcal{C}^{(1)}=\mathcal{C}$. Let
$\varphi$ be a $t$-fold colouring of $G(\mathcal{C}^{(1)})$. There exists a
probe $P$ such that $|\varphi(\mathcal{S}(P))|\geq s$ by assumption on
$\mathcal{C}$. Since every segment of $\mathcal{S}(P)$ crosses the only pillar
$I$ of $P$ vertically, $|\varphi(\mathcal{S}(I))|\geq s$. Therefore,
$P^{\prime}=P$ verifies the conclusion of Lemma 2.

Suppose that $k\geq 2$. Let $\varphi$ be a $t$-fold colouring of
$G(\mathcal{C}^{(k)})$. By the inductive hypothesis, there exists a probe $P$
of $\mathcal{C}^{(k-1)}$ such that for every $i\in\\{0,\dots,k-2\\}$, every
pillar $I^{P}_{i}$ of $P$ verifies
$|\varphi|_{\mathcal{S}^{(k-1)}}(\mathcal{S}^{(k-1)}(I_{i}^{P}))|\geq s$. By
the definition of $\mathcal{C}^{(k)}$, there exists a square $R_{P}$ in a root
of $P$ with an $R_{P}$-scaled copy
$\mathcal{C}_{P}=(\mathcal{S}_{P},\mathcal{P}_{P})$ of $\mathcal{C}$. By
assumption on $\mathcal{C}$, there exists a probe
$P^{\prime}\in\mathcal{P}_{P}\subseteq\mathcal{P}^{(k)}$ such that
$|\varphi|_{\mathcal{S}_{P}}(\mathcal{S}_{P}(P^{\prime}))|\geq s$. Since every
segment of $\mathcal{S}_{P}(P^{\prime})$ crosses $I^{P^{\prime}}_{k-1}$
vertically,
$|\varphi(\mathcal{S}^{(k)}(I^{P^{\prime}}_{k-1}))|\geq|\varphi|_{\mathcal{S}_{P}}(\mathcal{S}_{P}(I^{P^{\prime}}_{k-1}))|\geq|\varphi|_{\mathcal{S}_{P}}(\mathcal{S}_{P}(P^{\prime}))|\geq
s$. For every $i\in\\{0,\dots,k-2\\}$, every segment of
$\mathcal{S}^{(k-1)}(I_{i}^{P})\subseteq\mathcal{S}^{(k)}(I_{i}^{P})$ crosses
the pillar $I^{P^{\prime}}_{i}$ vertically. Therefore, we also have
$|\varphi(\mathcal{S}^{(k)}(I^{P^{\prime}}_{i}))|\geq|\varphi|_{\mathcal{S}^{(k-1)}}(\mathcal{S}^{(k-1)}(I_{i}^{P}))|\geq
s$. ∎

##  3 Lower bound for even $\omega$

Since the fractional chromatic number is a lower bound for the chromatic
number, the following result gives a construction to certify a lower bound for
the $\chi$-binding function for $d$-DIR in the case of even clique numbers,
which together with the trivial upper bound establishes the even case in
Theorem 1.

######  Theorem 3.

For all positive integers $t$ and $d$, there exists a triangle-free
configuration $\mathcal{C}_{t,d}=(\mathcal{S}_{t,d},\mathcal{P}_{t,d})$ with
slope number at most $d$ such that for every $t$-fold colouring $\varphi$ of
$G(\mathcal{C}_{t,d})$, there exists a probe $P\in\mathcal{P}_{t,d}$ such that
$|\varphi(\mathcal{S}_{t,d}(P))|\geq 2td$.

###### Proof.

We proceed by induction on $d$. For $d=0$, the configuration
$(\emptyset,\\{\mathcal{U}\\})$ satisfies the statement of the theorem.

Suppose that $d>0$ and that $\mathcal{C}_{t,d-1}$ is already constructed. Let
$\mathcal{H}=\mathcal{C}_{t,d-1}^{(4t+1)}=(\mathcal{S}_{\mathcal{H}},\mathcal{P}_{\mathcal{H}})$.
Let $\Gamma$ be the set of the slopes of the segments in
$\mathcal{S}_{t,d-1}$. We define the slope $\gamma$ as the minimum aspect
ratio over all probes of $\mathcal{P}_{\mathcal{H}}$, divided by $4t$.

We will construct a family of configurations
$\mathcal{H}_{i}=(\mathcal{S}_{i},\mathcal{P}_{i})$ for all $i\geq 0$ such
that

  1. 1.

for every segment $S\in\mathcal{S}_{i}$, the slope of $S$ is in
$\Gamma\cup\\{\gamma\\}$, and

  2. 2.

for every $t$-fold colouring $\varphi$ of $G(\mathcal{H}_{i})$, there is a
probe $P\in\mathcal{P}_{i}$ such that $|\varphi(\mathcal{S}_{i}(P))|\geq
2t(d-1)+2t(1-\frac{1}{2^{i}})$.

For $i=\left\lfloor\log(2t)\right\rfloor+1$, Item 2 implies that
$|\varphi(\mathcal{S}_{i}(P))|\geq 2td$, and so it suffices to take
$\mathcal{C}_{t,d}=\mathcal{H}_{i}$.

We build $\mathcal{H}_{i}$ as follows. For $i=0$, we take
$\mathcal{H}_{0}=\mathcal{C}_{t,d-1}$. Item 1 holds by definition of
$\mathcal{H}_{0}$ and Item 2 holds by the inductive hypothesis on
$\mathcal{C}_{t,d-1}$.

Now, assume that $i>0$. We will build $\mathcal{S}_{i}$ and $\mathcal{P}_{i}$
iteratively. Initialise $\mathcal{S}_{i}$ to $\mathcal{S}_{i-1}$ and
$\mathcal{P}_{i}$ to $\emptyset$. For each probe $P\in\mathcal{P}_{i-1}$, let
$R$ be a square in a root of $P$, and add an $R$-scaled copy $\mathcal{H}_{P}$
of $\mathcal{H}$ in $R$. For every probe $Q$ in $\mathcal{H}_{P}$, we divide
$Q$ vertically into $4t$ rectangles of equal height with the same width as
$Q$. We call these rectangles the _layers_ of $Q$. Let
$(L_{j}(Q))_{j\in\\{0,\dots,4t-1\\}}$ be the layers of $Q$ starting from the
top.

First, we add the top layer $L_{0}(Q)$ to $\mathcal{P}_{i}$ as a single probe.
Then, for every $j\in\\{1,\dots,4t-1\\}$, we add two segments in the interior
of $L_{j}(Q)$ to $\mathcal{S}_{i}$, with slope $\gamma$, that intersect at
exactly one point: $D^{j}_{1}$ crossing exactly the pillars
$I^{Q}_{j+1},\dots,I^{Q}_{4t}$ horizontally, and $D^{j}_{2}$ crossing
$I^{Q}_{j}$ horizontally and no other pillars. Since the slope of the diagonal
of a layer is at least $\gamma$, such segments are well-defined. See Figure 2.

Figure 2: Layers of a probe $P$ drawn in green, with new segments $D_{1}^{j}$
and $D_{2}^{j}$. Example for $t=1$.

Finally, we add to $\mathcal{P}_{i}$ two probes $P_{D^{j}_{1}},P_{D^{j}_{2}}$,
with $P_{D^{j}_{1}}$ crossed vertically by exactly $D^{j}_{1}$ and
$I^{Q}_{0},\dots,I^{Q}_{j}$, and $P_{D^{j}_{2}}$ crossed vertically by exactly
$D^{j}_{2}$ and $I^{Q}_{0},\dots,I^{Q}_{j-1}$. See Figure 3.

Figure 3: The two new probes $P_{D^{j}_{1}}$ and $P_{D^{j}_{2}}$ inside the
layer $L_{j}(P)$.

It follows from the construction that $\mathcal{P}_{i}$ is a set of probes for
$\mathcal{S}_{i}$, and that every segment in $\mathcal{S}_{i}$ has its slope
in $\Gamma\cup\\{\gamma\\}$ so Item 1 holds. It remains to prove that for
every $t$-fold colouring $\varphi$, there is a probe $P\in\mathcal{P}_{i}$
such that $|\varphi(\mathcal{S}_{i}(P))|\geq 2t(d-1)+2t(1-\frac{1}{2^{i}})$.
Let $\varphi$ be a $t$-fold colouring of $G(\mathcal{H}_{i})$. By the
inductive hypothesis, there exists $P\in\mathcal{P}_{i-1}$ such that
$|\varphi(\mathcal{S}_{i-1}(P))|\geq 2t(d-1)+2t(1-\frac{1}{2^{i-1}})$. By
Lemma 2 applied to $\mathcal{H}=\mathcal{C}_{t,d-1}^{(4t+1)}$, there exists a
probe $Q$ of $\mathcal{H}_{P}$ such that every pillar $I^{Q}_{j}$ verifies
$|\varphi(\mathcal{S}_{i}(I^{Q}_{j}))|\geq 2t(d-1)$. For every
$j\in\\{0,\dots,4t-1\\}$, let $\Phi_{j}=\varphi(\mathcal{S}_{i}(I^{Q}_{j}))$.
Recall that the top layer $L_{0}(Q)$ was added as a probe, and it crosses all
the $I^{Q}_{j}$s horizontally. If it contains at least
$2t(d-1)+2t(1-\frac{1}{2^{i}})$ colours, then this probe satisfies Item 2. So,
from now on, we may assume that $Q$ contains fewer than
$2t(d-1)+2t(1-\frac{1}{2^{i}})$ colours. Since $|\Phi_{0}|\geq 2t(d-1)$, we
have $2t(d-1)+2t(1-\frac{1}{2^{i}})-|\Phi_{0}|<2t$. Therefore, at most $2t-1$
indices $j\in\\{1,\dots,4t-1\\}$ are such that the set $\Phi_{j}$ contains a
colour not in $\bigcup_{j^{\prime}\leq j-1}\Phi_{j^{\prime}}$. Thus, for at
least $4t-1-2t+1=2t$ indices $j\in\\{1,\dots,4t-1\\}$,
$\Phi_{j}\subseteq\bigcup_{j^{\prime}\leq j-1}\Phi_{j^{\prime}}$.
Symmetrically, for at least $2t$ indices $j\in\\{1,\dots,4t-1\\}$, we have
$\Phi_{j}\subseteq\bigcup_{j^{\prime}\geq j+1}\Phi_{j^{\prime}}$. Thus, there
is an index $j_{0}\in\\{1,\dots,4t-1\\}$ such that
$\Phi_{j_{0}}\subseteq\bigcup_{j^{\prime}\geq j_{0}+1}\Phi_{j^{\prime}}$ and
$\Phi_{j_{0}}\subseteq\bigcup_{j^{\prime}\leq j_{0}-1}\Phi_{j^{\prime}}$. Let
$A=\Phi_{j_{0}}$, $B=\bigcup_{j^{\prime}\leq j_{0}-1}\Phi_{j^{\prime}}$ and
$C=\bigcup_{j^{\prime}\geq j_{0}+1}\Phi_{j^{\prime}}$. We have $A\subseteq B$
and $A\subseteq C$. Consider the layer $L_{j_{0}}(Q)$ and the corresponding
segments $D_{1}^{j_{0}},D_{2}^{j_{0}}$. Since $D_{1}^{j_{0}}$ and
$D_{2}^{j_{0}}$ share a common point,
$\varphi(D_{1}^{j_{0}})\cap\varphi(D_{2}^{j_{0}})=\emptyset$. Since
$D_{1}^{j_{0}}$ crosses $I^{Q}_{j_{0}+1},\dots,I^{Q}_{4t}$ horizontally, we
have $\varphi(D_{1}^{j_{0}})\cap C=\emptyset$. Since $A\subseteq C$, we also
have $\varphi(D^{j_{0}}_{1})\cap A=\emptyset$. Moreover, $D_{2}^{j_{0}}$
crosses $I^{Q}_{j_{0}}$ horizontally, so $\varphi(D^{j_{0}}_{2})\cap
A=\emptyset$. As a result, $\varphi(D^{j_{0}}_{1})$, $\varphi(D^{j_{0}}_{2})$,
and $A$ are pairwise disjoint. Thus,
$|\varphi(D^{j_{0}}_{1})\cup\varphi(D^{j_{0}}_{2})\cup
A|=|\varphi(D^{j_{0}}_{1})|+|\varphi(D_{2}^{j_{0}})|+|A|\geq t+t+2t(d-1)=2td$.
Hence, letting $Z_{i-1}=\varphi(\mathcal{S}_{i-1}(P))$, we have
$|(\varphi(D^{j_{0}}_{1})\cup\varphi(D^{j_{0}}_{2})\cup A)\setminus
Z_{i-1}|\geq 2td-|Z_{i-1}|$. Therefore, there is some $\alpha\in\\{1,2\\}$
such that $|(\varphi(D^{j_{0}}_{\alpha})\cup A)\setminus
Z_{i-1}|\geq\frac{2td-|Z_{i-1}|}{2}$. It follows that

$|\varphi(D^{j_{0}}_{\alpha})\cup A\cup
Z_{i-1}|\geq\frac{2td+|Z_{i-1}|}{2}\geq
2t(d-1)+2t\left(1-\frac{1}{2^{i}}\right).$

If $\alpha=1$, then $\varphi(\mathcal{S}_{i}(P_{D^{j_{0}}_{1}}))$ contains at
least $|\varphi(D^{j_{0}}_{1})\cup B\cup
Z_{i-1}|\geq|\varphi(D^{j_{0}}_{1})\cup A\cup Z_{i-1}|\geq
2t(d-1)+2t(1-\frac{1}{2^{i}})$ colours. The same lower bound holds for
$\varphi(\mathcal{S}_{i}(P_{D^{j_{0}}_{2}}))$ by a similar argument when
$\alpha=2$. Finally, Item 2 always holds for $\mathcal{H}_{i}$. This concludes
the proof of the theorem. ∎

######  Corollary 4.

For all positive integers $t$ and $d$, there exists a multiset of segments
$\mathcal{S}^{\prime}_{t,d}\subseteq\mathcal{U}$ with slope number at most $d$
such that $\omega(G(\mathcal{S}^{\prime}_{t,d}))=2t$ and
$\chi(G(\mathcal{S}^{\prime}_{t,d}))\geq 2td$.

###### Proof.

Let $\mathcal{C}_{t,d}=(\mathcal{S}_{t,d},\mathcal{P}_{t,d})$ be a
configuration given by Theorem 3. Let $\mathcal{S}^{\prime}_{t,d}$ be a
$t$-blowup of $\mathcal{S}_{t,d}$ and for every $v\in\mathcal{S}_{t,d}$, let
$\\{v_{1},\cdots,v_{t}\\}$ be the segments of $\mathcal{S}^{\prime}_{t,d}$
corresponding to the $t$-blowup of $v$. Since the graph $G(\mathcal{S}_{t,d})$
is triangle-free, we have $\omega(G(\mathcal{S}^{\prime}_{t,d}))=2t$. Let
$\varphi$ be a colouring of $G(\mathcal{S}^{\prime}_{t,d})$. The colouring
$\varphi$ corresponds to a $t$-fold colouring $\varphi_{t}$ of
$G(\mathcal{S}_{t,d})$ such that for all $v\in V(G(\mathcal{S}_{t,d}))$,
$\varphi_{t}(v)=\bigcup_{i\in\\{1,\cdots,t\\}}\varphi(v_{i})$. By Theorem 3,
there exists a probe $P\in\mathcal{P}_{t,d}$ such that
$|\varphi_{t}(\mathcal{S}_{t,d}(P))|\geq 2td$. Hence, by definition of
$\varphi_{t}$, $\varphi$ uses at least $2td$ colours as desired. ∎

##  4 Lower bound for odd $\omega$

The construction of Theorem 3 is obtained from a $t$-blowup of a triangle-free
$d$-DIR graph which results in a graph with clique number $2t$. To certify the
lower bound for the $\chi$-binding function in the case of odd clique numbers,
we rely on the same construction to get a $(d-1)$-DIR graph and modify the
last set of segments to obtain a $d$-DIR graph with odd clique number.

######  Theorem 5.

For every nonnegative integer $t$ and every positive integer $d$, there exists
a multiset of segments $\mathcal{S}^{\prime\prime}_{t,d}$ with slope number at
most $d$ such that $\omega(G(\mathcal{S}^{\prime\prime}_{t,d}))=2t+1$ and
$\chi(G(\mathcal{S}^{\prime\prime}_{t,d}))\geq 2td+1$.

###### Proof.

If $t=0$, then a single segment satisfies the conclusion of the theorem. Now,
assume that $t>0$.

By Theorem 3, there exists a triangle-free configuration
$\mathcal{C}_{t,d-1}=(\mathcal{S}_{t,d-1},\mathcal{P}_{t,d-1})$ with slope
number at most $d-1$ such that for every $t$-fold colouring $\varphi$ of
$G(\mathcal{C}_{t,d-1})$, there exists a probe $P\in\mathcal{P}_{t,d-1}$ such
that $|\varphi(\mathcal{S}_{t,d-1}(P))|\geq 2t(d-1)$.

Let
$\mathcal{H}=\mathcal{C}_{t,d-1}^{(2t+3)}=(\mathcal{S}_{\mathcal{H}},\mathcal{P}_{\mathcal{H}})$.
Let $\Gamma$ be the set of the slopes of the segments in
$\mathcal{S}_{t,d-1}$. We define the slope $\gamma$ as the minimum aspect
ratio over all probes of $\mathcal{P}_{\mathcal{H}}$, divided by $2t+1$. Let
$\mathcal{S}_{\mathcal{H},t}$ be the $t$-blowup of
$\mathcal{S}_{\mathcal{H}}$.

We construct the multiset $\mathcal{S}^{\prime\prime}_{t,d}$ of segments as
follows. Initialise $\mathcal{S}^{\prime\prime}_{t,d}$ with
$\mathcal{S}_{\mathcal{H},t}$. For every probe $Q$ in $\mathcal{H}$, we divide
$Q$ vertically into $2t+1$ layers similarly to the construction in the proof
of Theorem 3. For $j\in\\{1,\dots,2t+1\\}$, let $L_{j}(Q)$ be the $j$th layer
of $Q$ starting from the top. For every $j\in\\{1,\dots,2t+1\\}$, add $t+1$
coinciding segments $(D_{1,\ell}^{j})_{\ell\in\\{1,\dots,t+1\\}}$ with slope
$\gamma$ in the interior of $L_{j}(Q)$ crossing exactly the pillars
$I^{Q}_{j+1},\dots,I^{Q}_{2t+2}$ horizontally, and $t$ coinciding segments
$(D_{2,\ell}^{j})_{\ell\in\\{1,\dots,t\\}}$ with slope $\gamma$ in the
interior of $L_{j}(Q)$ crossing the pillar $I^{Q}_{j}$ horizontally and no
other pillars, such that $D_{1,\ell}^{j}$ and $D_{2,\ell^{\prime}}^{j}$
intersect in exactly one point, which is the same for every pair
$\ell\in\\{1,\dots,t+1\\}$ and $\ell^{\prime}\in\\{1,\dots,t\\}$. Observe that
$G(\mathcal{S}^{\prime\prime}_{t,d})$ has clique number $2t+1$.

Now, we prove that in every colouring of
$G(\mathcal{S}^{\prime\prime}_{t,d})$, at least $2td+1$ colours are used. Let
$\varphi$ be a colouring of $G(\mathcal{S}^{\prime\prime}_{t,d})$. If
$|\varphi(\mathcal{S}^{\prime\prime}_{t,d})|\geq 2td+1$, then the theorem
holds. Otherwise, let $\varphi_{t}$ be the $t$-fold colouring of
$G(\mathcal{S}_{\mathcal{H}})$ corresponding to
$\varphi|_{\mathcal{S}_{\mathcal{H},t}}$. By Lemma 2, there exists a probe
$Q\in\mathcal{P}_{\mathcal{H}}$ such that for every pillar $I$ of $Q$,
$|\varphi_{t}(\mathcal{S}_{\mathcal{H}}(I))|\geq 2t(d-1)$. Since the total
number of colours used by $\varphi$ is at most $2td$, we deduce that
$\varphi(\mathcal{S}^{\prime\prime}_{t,d}(I^{Q}_{j}))$ contains a colour not
in $\bigcup_{j^{\prime}\geq
j+1}\varphi(\mathcal{S}^{\prime\prime}_{t,d}(I^{Q}_{j^{\prime}}))$ for at most
$2t$ values of $j\in\\{1,\dots,2t+1\\}$. Thus there is an index
$j_{0}\in\\{1,\dots,2t+1\\}$ such that
$\varphi(\mathcal{S}^{\prime\prime}_{t,d}(I^{Q}_{j_{0}})\subseteq\bigcup_{j^{\prime}\geq
j_{0}+1}\varphi(\mathcal{S}^{\prime\prime}_{t,d}(I^{Q}_{j^{\prime}}))$. Let
$A=\varphi(\mathcal{S}^{\prime\prime}_{t,d}(I^{Q}_{j_{0}}))$ and let
$B=\bigcup_{j^{\prime}\geq
j_{0}+1}\varphi(\mathcal{S}^{\prime\prime}_{t,d}(I^{Q}_{j^{\prime}}))$. Let
$\Phi_{1}=\\{\varphi(D^{j_{0}}_{1,\ell})\mid\ell\in\\{1,\dots,t+1\\}\\}$ and
let $\Phi_{2}=\\{\varphi(D^{j_{0}}_{2,\ell})\mid\ell\in\\{1,\dots,t\\}\\}$.
Similarly to the reasoning in the proof of Theorem 3, $\Phi_{1}$ and
$\Phi_{2}$ are disjoint due to the common point shared by the segments in
$(D^{j_{0}}_{1,\ell})_{\ell}$ and the ones in
$(D^{j_{0}}_{2,\ell^{\prime}})_{\ell^{\prime}}$, $\Phi_{1}$ and $B$ are
disjoint because the segments of $(D^{j_{0}}_{1,\ell})_{\ell}$ cross
$I_{j^{\prime}}^{Q}$ horizontally for $j^{\prime}\geq j_{0}+1$ (and since
$A\subseteq B$, we also have that $\Phi_{1}$ and $A$ are disjoint), and
$\Phi_{2}$ and $A$ are disjoint since since the segments of
$(D^{j_{0}}_{2,\ell^{\prime}})_{\ell^{\prime}}$ cross $I_{j_{0}}^{Q}$
horizontally. Therefore, $\Phi_{1}$, $\Phi_{2}$, and $A$ are pairwise disjoint
so $|\Phi_{1}\cup\Phi_{2}\cup A|\geq(t+1)+t+2t(d-1)=2td+1$. Finally, $\varphi$
has to use at least $2td+1$ colours and this concludes the proof of the
theorem. ∎

##  5 Upper bound for odd $\omega$

In this section, we upper bound the $\chi$-binding function for $d$-DIR in the
case of odd clique numbers, which combined with the result of the previous
section settles the odd case in Theorem 1.

Let $G$ be an interval graph and let $\mathcal{I}=(I_{v}\mid v\in V(G))$ be an
interval representation of $G$. Let $w$ be an integer with $w\geq\omega(G)$.
For any $x\in\mathcal{I}$, we define the set $S_{x}=\\{u\in V(G)\mid x\in
I_{u}\\}$ of vertices corresponding to intervals containing $x$. A vertex $v$
of $G$ is said to be _$w$ -special_ if there exists $x\in I_{v}$ such that
$|S_{x}|\leq\frac{w-1}{2}$. Observe that $S_{x}$ consists of a clique of
$w$-special vertices only.

######  Lemma 6.

Let $G$ be an interval graph with clique number at most $w$. There is a
colouring $\varphi:V(G)\to\\{0,\dots,w-1\\}$ of $G$ such that $\varphi(v)\neq
0$ for every $w$-special vertex $v$.

###### Proof.

Suppose for a contradiction that there exists a counterexample $G$, and
moreover choose one with $|V(G)|$ minimal. Let $\mathcal{I}=(I_{v}\mid v\in
V(G))$ be an interval representation of $G$. We deal with two cases according
to the existence of some $w$-special vertices “splitting” $G$.

Suppose there exists a small clique of $w$-special vertices that “separates
$G$ into a non-empty left side and non-empty right side”. Formally, suppose
that there exists a point $x\in\mathbb{R}$ such that $\\{I\in\mathcal{I}\mid
I\subseteq(-\infty,x)\\}$ and $\\{I\in\mathcal{I}\mid
I\subseteq(x,+\infty)\\}$ are non-empty, and the set $S_{x}=\\{u\in V(G)\mid
x\in I_{u}\\}$ has size at most $\frac{w-1}{2}$. Then vertices in $S_{x}$ are
$w$-special by definition. Let $G_{\ell}$ and $G_{r}$ be the subgraphs of $G$
induced by intervals intersecting $(-\infty,x]$ and $[x,+\infty)$,
respectively. By minimality of $|V(G)|$, there are $w$-colourings
$\varphi_{\ell}$ and $\varphi_{r}$ of $G_{\ell}$ and $G_{r}$, respectively,
such that $w$-special vertices are not coloured $0$. We show how to combine
these colourings into one for $G$. Note first that $w$-special vertices in
$G$, when applicable, are also $w$-special in $G_{\ell}$ and $G_{r}$. In
particular, $S_{x}$ consists only of $w$-special vertices, which are not
coloured $0$ by both $\varphi_{\ell}$ and $\varphi_{r}$. By definition
$S_{x}=V(G_{\ell})\cap V(G_{r})$, so up to permuting the colours in
$\\{1,2,\dots,w-1\\}$ for one of the colourings, we can assume that
$\varphi_{\ell}(u)=\varphi_{r}(u)$ for every $u\in V(G_{\ell})\cap V(G_{r})$.
Then, colouring $\varphi$ defined by $\varphi(u)=\varphi_{\ell}(u)$ for every
$u\in V(G_{\ell})$ and $\varphi(u)=\varphi_{r}(u)$ for every $u\in V(G_{r})$
is a $w$-colouring of $G$ such that no $w$-special vertices are coloured $0$.

If there exist no such separating sets, then every $w$-special vertex $u$ is
“leftmost” or “rightmost” in $\mathcal{I}$. Formally, $u$ is such that
$\min(I_{u})\leq\min_{v\in V(G)}\max(I_{v})$ or $\max(I_{u})\geq\max_{v\in
V(G)}\min(I_{v})$. This implies that there are at most $2\frac{w-1}{2}=w-1$
$w$-special vertices. Since $G$ is an interval graph and $w\geq\omega(G)$,
there exists a $w$-colouring of $G$. Then, at least one colour is not used by
the $w$-special vertices, letting us permute it with colour $0$ to obtain a
colouring where no $w$-special vertices are coloured $0$. ∎

######  Theorem 7.

For any graph $G$ in $d$-DIR, if $\omega(G)$ is odd, then $\chi(G)\leq
d(\omega(G)-1)+1$.

###### Proof.

Let $(I_{u}\mid u\in V(G))$ be a $d$-DIR representation of $G$. Let
$V_{1},\dots,V_{d}$ be the partition of $V(G)$ according to the slopes of the
segments in its $d$-DIR representation. For every $i\in\\{1,2,\dots,d\\}$,
$G[V_{i}]$ is an interval graph and $\omega(G)\geq\omega(G[V_{i}])$. So by
Lemma 6, there is a colouring $\varphi_{i}$ of $G[V_{i}]$ using the colours
$0,1,2,\dots,\omega(G)-1$ and no $\omega(G)$-special vertices of $G[V_{i}]$
are coloured $0$. For every $i\in\\{1,\dots,d\\}$ and for every $v\in V_{i}$,
let $\varphi(v)=(i,\varphi_{i}(v))$ if $\varphi_{i}(v)\neq 0$, and
$\varphi(v)=0$ otherwise. We claim that $\varphi$ is a
$(d(\omega(G)-1)+1)$-colouring of $G$. Indeed, if $uv$ is an edge in $G$ such
that $\varphi(u)=\varphi(v)$, then $\varphi(u)=\varphi(v)=0$. In other words,
$u$ and $v$ are both non-special vertices and are in distinct $V_{i}$s. Let
$i_{u},i_{v}\in\\{1,\dots,d\\}$ such that $u\in V_{i_{u}}$ and $v\in
V_{i_{v}}$. Since $\omega(G)$ is odd, the intersection point $x$ of $I_{u}$
and $I_{v}$ is included in at least $\frac{\omega(G)+1}{2}$ intervals
corresponding to vertices in $V_{i_{u}}$ and at least $\frac{\omega(G)+1}{2}$
intervals corresponding to vertices in $V_{i_{v}}$. This gives a clique in $G$
of order $\omega(G)+1$, a contradiction. ∎

##  6 Concluding remarks

Recall that the Hall ratio $\rho(G)$ of a graph $G$ is defined by
$\rho(G)=\max_{H\subseteq G}\frac{|V(H)|}{\alpha(H)}$, where $\alpha$ denotes
the independence number. Note that $\omega(G)\leq\rho(G)\leq\chi(G)$ for all
$G$, and it was remarked in [CGL06] how $\rho$ is bounded while $\chi$ is
unbounded for a certain sequence of Kneser graphs. Can we find constructions
to certify the same lower bounds as in Theorem 1 but for $\rho$ instead of
$\chi$? In particular, for every $d$ and even $\omega$ is there a
$d$-directional segment graph of clique number $\omega$ with $\rho\geq
d\omega$? Or a potentially easier version is the Hall ratio analogue of
Erdős’s question: are there triangle-free segment graphs of arbitrarily large
$\rho$? We remark that Walczak [Wal15] settled a similar, weaker version of
this last question.

A possible generalisation of our problem is to consider rectangles instead of
segments. In a similar manner, we can introduce the notion of the
$d$-directional rectangle graphs: consider a set $d$ non-parallel lines and
any set of rectangles such that each of them has one of the sides parallel to
one of the given lines. We want to find the $\chi$-bounding function of such
graphs.

This problem has been quite extensively studied in the case of axis-parallel
rectangles (i.e. $d=1$) and thanks to Chalermsook and Walczak [CW21] it is
known that in this case $O(\omega\log\omega)$ colours always suffice; however,
the lower bound remains $\Omega(\omega)$. This implies that for any $d$, no
more than $O(d\omega\log\omega)$ colours are needed, and our construction from
this paper can be easily adapted (by replacing the segments with “thin enough”
rectangles) to show a lower bound of $\omega\cdot(d+o(1))$. The gap between
linear and log-linear function remains open, though, in both $d=1$ and the
general case.

#### Acknowledgement.

This work was initiated during the Sparse (Graphs) Coalition session,
$\chi$-boundedness, organised by James Davies, Bartosz Walczak, and the second
author. Our team thanks the organisers and participants for the conducive
working atmosphere.

#### Open access statement.

For the purpose of open access, a CC BY public copyright license is applied to
any Author Accepted Manuscript (AAM) arising from this submission.

## References

  * [AG60] E. Asplund and B. Grünbaum.  On a coloring problem.  Math. Scand., 8:181–188, 1960.
  * [BDN23] Sudatta Bhattacharya, Zdeněk Dvořák, and Fariba Noorizadeh.  Chromatic number of intersection graphs of segments with two slopes.  In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB23), 2023.
  * [Bur65] James P. Burling.  On coloring problems of families of prototypes.  PhD thesis, University of Colorado, Boulder, 1965.
  * [CGL06] Mathew Cropper, András Gyárfás, and Jenő Lehel.  Hall ratio of the Mycielski graphs.  Discrete Math., 306(16):1988–1990, 2006.
  * [CW21] Parinya Chalermsook and Bartosz Walczak.  Coloring and maximum weight independent set of rectangles.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 860–868. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2021.
  * [Gyá87] A. Gyárfás.  Problems from the world surrounding perfect graphs.  In Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), volume 19, pages 413–441 (1988), 1987.
  * [KN95] Alexandr Kostochka and Jaroslav Nešetřil.  Chromatic number of geometric intersection graphs.  In Proceedings of the Prague Midsummer Combinatorial Workshop (Charles University, Prague), volume 95–309, pages 43–45, 1995.
  * [McG00] Sean McGuinness.  Colouring arcwise connected sets in the plane. I.  Graphs Combin., 16(4):429–439, 2000.
  * [MM99] Terry A. McKee and F. R. McMorris.  Topics in intersection graph theory.  SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999.
  * [PKK+14] Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, and Bartosz Walczak.  Triangle-free intersection graphs of line segments with large chromatic number.  J. Combin. Theory Ser. B, 105:6–10, 2014.
  * [Spi03] Jeremy P. Spinrad.  Efficient graph representations, volume 19 of Fields Institute Monographs.  American Mathematical Society, Providence, RI, 2003.
  * [SS20] Alex Scott and Paul Seymour.  A survey of $\chi$-boundedness.  J. Graph Theory, 95(3):473–504, 2020.
  * [Suk14] Andrew Suk.  Coloring intersection graphs of $x$-monotone curves in the plane.  Combinatorica, 34(4):487–505, 2014.
  * [Wal15] Bartosz Walczak.  Triangle-free geometric intersection graphs with no large independent sets.  Discrete Comput. Geom., 53(1):221–225, 2015.