# The Maximum Chromatic Number of the Disjointness Graph of Segments on
$n$-point Sets in the Plane with $n\leq 16$

J. J. García-Davila  J. Leaños  M. Lomelí-Haro  Instituto de Física y
Matemáticas, Universidad Tecnológica de la Mixteca, México,
<EMAIL_ADDRESS>L. M. Ríos-Castro  Academia de Físico–Matemáticas,
Instituto Politécnico Nacional, CECYT 18, México<EMAIL_ADDRESS>
###### Abstract

Let $P$ be a finite set of points in general position in the plane. The
disjointness graph of segments $D(P)$ of $P$ is the graph whose vertices are
all the closed straight line segments with endpoints in $P$, two of which are
adjacent in $D(P)$ if and only if they are disjoint. As usual, we use
$\chi(D(P))$ to denote the chromatic number of $D(P)$, and use $d(n)$ to
denote the maximum $\chi(D(P))$ taken over all sets $P$ of $n$ points in
general position in the plane. In this paper we show that $d(n)=n-2$ if and
only if $n\in\\{3,4,\ldots,16\\}$.

Keywords: Chromatic number, Disjointness graph of segments, Complete geometric
graphs.

##  1 Introduction

The chromatic number of a graph $G$ is the minimum number of colors needed to
color its vertices so that adjacent vertices receive different colors; it is
denoted by $\chi(G)$. For $k,n\in{\mathbb{Z}}^{+}$ with $k\leq n/2$, the
Kneser graph $KG(n,k)$ has as its vertices the $k$-subsets of
$\\{1,2,\ldots,n\\}$ and two of such $k$-subsets form an edge if and only if
they are disjoint. Kneser conjectured [11] in 1956 that
$\chi(KG(n,k))=n-2k+2$. This conjecture was proved by Lovász [12] and
independently by Bárány [5] in $1978$.

Let $P$ be a set of $n\geq 2$ points in general position in the plane, and let
${\cal P}$ be the set of all $\binom{n}{2}$ closed straight line segments with
endpoints in $P$. The disjointness graph of segments $D(P)$ of $P$ is the
graph whose vertex set is ${\cal P}$, and two elements of ${\cal P}$ are
adjacent if and only if their corresponding segments are disjoint. See Figure
1 for an example.

The disjointness graph of segments $D(P)$ was introduced in $2005$ by Araujo
et al. [4], as a geometric version of the Kneser graph $KG(n,k)$ for $k=2$. It
follows from the definitions of $KG(n,2)$ and $D(P)$ that if $|P|=n\geq 2$,
then both have size $\binom{n}{2}$ and $KG(n,2)$ contains a subgraph which is
isomorphic to $D(P)$. Similarly, we note that the crossings between segments
of $\mathcal{P}$ are responsible for the edges of $KG(n,2)$ that are not in
$D(P)$. Indeed, suppose that $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ and consider
the natural bijection $f(i)\to p_{i}$ between $\\{1,2,\ldots,n\\}$ and $P$.
Note that if $\\{i,j\\}$ and $\\{k,l\\}$ are adjacent in $KG(n,2)$, then the
corresponding segments of $\mathcal{P}$ defined by $\\{p_{i},p_{j}\\}$ and
$\\{p_{k},p_{l}\\}$ are also adjacent in $D(P)$, unless they cross each other.
In a nutshell, the difference between $KG(n,2)$ and $D(P)$ is completely
determined by the crossings between segments of $\mathcal{P}$. On the other
hand, in [1] it was proved that the number of crossings in $\mathcal{P}$ grows
at least $0.37997\binom{n}{4}+\Theta(n^{3})$, and so the number of edges that
are in $KG(n,2)$ but not in $D(P)$ is linear in the number of edges of
$KG(n,2)$.

It is natural to ask about Kneser's conjecture in the context of the
disjointness graph of segments. Since $D(P)$ is a subgraph of $KG(n,2)$, it is
clear that $\chi(D(P))\leq\chi(KG(n,2))=n-2$. Moreover, since the number of
edges of $D(P)$ is significantly smaller than the number of edges of
$KG(n,2)$, one might expect that $\chi(D(P))<n-2$ most of the time.

For $n\in{\mathbb{Z}}^{+}$, let us define

$d(n):=\max\\{\chi(D(P))~{}:~{}P\text{ is an }n-\text{point set in general
position in the plane}\\}.$

The following questions arise naturally from the above discussion.

Question 1. For what values of $n$ is $d(n)=n-2$?

Question 2. More generally, What is the value of $d(n)$ for each
$n\in{\mathbb{Z}}^{+}$?

The systematic study of several combinatorial properties of $D(P)$ began with
the work of Araujo et al. in 2005 [4]. In particular, the following general
bounds for $d(n)$ with $n\geq 3$ were proved in [4],

$5\left\lfloor\frac{n}{7}\right\rfloor\leq
d(n)\leq\min\left\\{n-2,n+\frac{1}{2}-\frac{\lfloor\log\log(n)\rfloor}{2}\right\\}.$

We note that these inequalities imply that $d(7)=5$.

The problem of determining the chromatic number $\chi(D(P))$ of $D(P)$ remains
open in general. Furthermore, as far as we know, this problem has been solved
only for two families of points: the convex sets and the double chains.

For $m\in{\mathbb{Z}}^{+}$ we shall use $C_{m}$ to denote a set of $m$ points
in (general and) convex position in the plane. We recall that for
$k,l\in{\mathbb{Z}}^{+}$ a double chain $C_{k,l}$ is a $(k+l)$-point set in
general position in the plane such that $C_{k,l}$ is the dijoint union of
$C_{k}$ and $C_{l}$ where the points are located in such a way that any point
of $C_{k}$ (resp. $C_{l}$) is below (resp. above) every straight line spanned
by two points of $C_{l}$ (resp. $C_{k}$). In Figure 1($a$) the sets
$T_{1}=\\{t_{1}^{1},t_{1}^{2},t_{1}^{3}\\}$ and
$T_{2}=\\{t_{2}^{1},t_{2}^{2},t_{2}^{3}\\}$ are two instances of $C_{3}$, and
$T_{1}\cup T_{2}$ is an instance of $C_{3,3}$.

In [9] 2018 the exact value of $\chi(D(C_{n}))$ has been settled by Fabila-
Monroy, Jonsson, Valtr and Wood:

$\chi(D(C_{n}))=n-\left\lfloor\sqrt{2n+\frac{1}{4}}-\frac{1}{2}\right\rfloor.$

Similarly, in [8] 2020 Fabila-Monroy, Hidalgo-Toscano, Leaños and Lomelí-Haro
have shown that if $C_{k,l}$ is a double chain with $l\geq\max\\{3,k\\}$, then

$\chi(D(C_{k,l}))=k+l-\left\lfloor\sqrt{2l+\frac{1}{4}}-\frac{1}{2}\right\rfloor.$

Note that if $l=k$, then $\chi(D(C_{k,l}))$ provides the currently best lower
bound of $d(n)$, namely:

$d(n)\geq n-\left\lfloor\sqrt{n+\frac{1}{4}}-\frac{1}{2}\right\rfloor.$

As we shall see, the exact values of $\chi(D(C_{n}))$ and $\chi(D(C_{k,l}))$
will be useful in our proof. Another important fact that we use is a result
proved by Szekeres and Peters in [15] 2006, in which they confirmed the
following conjecture for $n=6$.

######  Conjecture 1 (Erdős and Zsekeres, 1935).

Any set of $2^{m-2}+1$ points in general position in the plane contains a
convex $m$-gon.

The study of the combinatorial properties of the disjointness graph of
segments and related graphs have received considerable attention lattely. For
more results about this kind of graphs we refer the reader to [2, 3, 4, 6, 10,
13, 14].

Our main objective in this paper is to give a full answer to the Question 1.
As we have mentioned above, by Lovász's theorem [12] and the fact that $D(P)$
is a subgraph of $KG(n,2)$, it follows that $\chi(D(P))\leq n-2$ whenever
$n=|P|\geq 2$. Our main result is the following theorem.

######  Theorem 2.

For $n\geq 2$ integer, let $d(n)$ be defined as above. Then $d(n)=n-2$ iff
$n\in\\{3,4,\ldots,16\\}$.

In view of the above discussion, it is clear that in order to show that
$d(n)=n-2$ for $n\in\\{3,4,\ldots,16\\}$, it suffices to exhibit an $n$-point
set $P$ in general position in the plane such that $\chi(D(P))=n-2$. The rest
of the paper is devoted to this end, and in fact the heart of our proof is to
show that any subset $X^{\prime}$ of the $16$-point set $X$ given in Figure 2,
satisfies the required inequality for each $|X^{\prime}|\geq 3$, namely that
$\chi(D(X^{\prime}))\geq|X^{\prime}|-2$.

In the early stages of this work, we were trying to attack this problem by
computer search, but soon we convinced ourselves that the number of colorings
of $D(X)$ that must be considered grows exponentially with the number of
vertices of $D(X)$. As we shall see later, a surprising fact that illustrates
the computational complexity of this problem is the following: $D(X)$ has a
subset $\mathcal{S}$ with at least 100 vertices such that if
$v\in\mathcal{S}$, then $D(X)\setminus\\{v\\}$ can be colored with only 13
colors.

The rest of the paper is organized as follows. In Section 2 we define the set
$X$ by means of the precise coordinates of its $16$ points, and give a brief
discussion on its geometric properties. In Section 3 we introduce some
notation and terminology that we shall use in most of the proofs. In Section 4
we present a summary of basic (or known) facts that we shall use in Section 5.
The more technical work of this paper is given in Section 5, there we prove
the main claims behind the proof of Theorem 2. Finally, in Section 6 we
establish Theorem 2 by combining in several ways the results stated in
previous sections.

Figure 1: ($a$) Let $T_{1}=\\{t_{1}^{1},t_{1}^{2},t_{1}^{3}\\}$ and
$T_{2}=\\{t_{2}^{1},t_{2}^{2},t_{2}^{3},\\}$. Then $T_{1}\cup T_{2}$ is a set
of 6 points in general position in the plane. Each of $T_{1}$ and $T_{2}$ is
an instance of $C_{3}$, and $T_{1}\cup T_{2}$ is an instance of the double
chain $C_{3,3}$. ($b$) This is the complete geometric graph
$\mathcal{T}_{1}\cup\mathcal{T}_{2}$ induced by $T_{1}\cup T_{2}$. The graph
in ($c$) is the disjointness graph of segments induced by $T_{1}\cup T_{2}$,
and we shall denote it by $D(T_{1}\cup T_{2})$.

##  2 The $16$-point set $X$

We recall that if $P$ and $Q$ are two finite point sets in general position in
the plane, then it is said they have the same order type iff there is a
bijection $f:P\to Q$ such that each ordered triple $abc$ in $P$ has the same
orientation as its image $f(a)f(b)f(c)$. We shall write $P\sim Q$ if $P$ and
$Q$ have the same order type. In particular, it is well known (see for
instance [1]) that if $P\sim Q$, then $D(P)$ and $D(Q)$ are isomorphic.

For the rest of the paper, $X$ denotes the $16$-point set given in Figure 2
and we will refer to its points according to the labelling depicted there. In
particular, we partition $X$ in the subsets $A,B,T_{1},T_{2}$, where
$A:=\\{a_{1},a_{2},\ldots,a_{5}\\}$, $B:=\\{b_{1},b_{2},\ldots,b_{5}\\}$,
$T_{1}:=\\{t^{1}_{1},t^{2}_{1},t^{3}_{1}\\}$ and
$T_{2}:=\\{t^{1}_{2},t^{2}_{2},t^{3}_{2}\\}$. We recall that $\mathcal{X}$ is
the set of $\binom{16}{2}$ closed straight line segments with endpoints in
$X$.

Figure 2: The $16$-point set defined by these coordinates is $X$. The ellipse
on the right is a zoom of the ellipse on the left. We will derive the proof of
Theorem 2 by showing that $\chi(D(X^{\prime}))=|X^{\prime}|-2$ for each
$X^{\prime}\subseteq X$ with $|X^{\prime}|\geq 3$. We remark that the
$6$-point set
$\\{t_{1}^{1},t_{1}^{2},t_{1}^{3},t_{2}^{1},t_{2}^{2},t_{2}^{3}\\}$ is the
same (order type) as those in Figure 1($a$)-($b$).

The following properties of $X$ are easy to check:

  * •

$X$ is $16$-point set in general position in the plane which has no $6-$points
forming a convex hexagon,

  * •

no segment of $\mathcal{X}$ is neither horizontal nor vertical,

  * •

each segment with endpoints in $T_{i}$ has negative slope for each
$i\in\\{1,2\\}$,

  * •

$A\cup B\sim C_{5,5}$, $A\cup T_{1}\sim C_{5,3}$, $T_{2}\cup B\sim C_{3,5}$,
$T_{1}\cup T_{2}\sim C_{3,3}$ and $A\cup T_{2}\sim B\cup T_{1}$.

From now on, we will use these properties of $X$ without explicit mention.

For $e\in\mathcal{X}$ we shall use $l(e)$ and $r(e)$ to denote the leftmost
and the rightmost point of $e$, respectively. Since $\mathcal{X}$ has no
vertical segments, then $l(e)$ and $r(e)$ are well-defined for each
$e\in\mathcal{X}$. Then $l(e)$ and $r(e)$ are points of $X$ and are the
endpoints of $e$. We remark that if $e$ has both endpoints in $T_{i}$ for some
$i\in\\{1,2\\}$, then $l(e)$ (resp. $r(e)$) is also the topmost (resp. lowest)
point of $e$.

##  3 Notational conventions and terminology

Our aim in this section is to introduce some useful notational conventions,
terminology and concepts that we shall use in the rest of the paper.

Throughout this section, $P$ denotes a set of $n\geq 2$ points in general
position in the plane. If $x$ and $y$ are distinct points of $P$, then we
shall use $xy$ to denote the closed straight line segment whose endpoints are
$x$ and $y$. If $R$ and $S$ are disjoint nonempty subsets of $P$, then
$R*S:=\\{xy~{}:~{}x\in R\mbox{ and }y\in S\\}$. We simply write $x*S$ (resp.
$R*y$) whenever $R=\\{x\\}$ (resp. $S=\\{y\\}$).

If $x,y,z$ are three distinct points of $P$, then we will refer to the
triangle formed by them in any of the following ways: $\Delta(x,y,z)$,
$\Delta(xy,z)$, $\Delta(xy,xz)$, etc.

We shall denote by $\overline{P}$ the boundary of the convex hull of $P$.

If $Q\subseteq P$ with $|Q|\geq 2$, then we shall use the font style
$\mathcal{Q}$ to denote the set of all $\binom{|Q|}{2}$ closed straight line
segments with endpoints in $Q$. We often make no distinction between the set
of segments $\mathcal{Q}$ and the complete geometric graph that it induces.

######  Note 1.

From the definition of $D(P)$ it follows that $\chi(D(P))$ is the minimum
number of colors in an edge-coloring of the complete geometric graph
$\mathcal{P}$ in which any two edges belonging to the same chromatic class
cross or are incident. We remark that all our proofs are given in terms of
this kind of edge-colorings of $\mathcal{P}$. Unless otherwise stated, from
now on, any coloring of $D(P)$ must be assumed to be an edge-coloring of the
complete geometric graph $\mathcal{P}$.

We classify each chromatic class $c$ of a given coloring $\gamma$ of
$\mathcal{P}$ as either thrackle or star. We call $c$ a thrackle if at least
two segments in $c$ cross each other, and otherwise $c$ is a star. If $c$ is a
star whose segments are incident with exactly $m$ points of $P$, then $c$ is
an $m$–star. Clearly, each $m$–star $c$ with $m\geq 3$ has a unique apex, i.e.
a point of $P$ that is incident with all the segments of $c$. If $c$ is a
$2$–star then $c$ consists of a singleton segment $e$, and in this case both
ends of $e$ are considered apices of $c$.

Let $\gamma$ be a coloring of $\mathcal{P}$ and let $Q\subseteq P$. For
exposition purposes, we abuse notation and use $\gamma(Q)$ to refer to the set
of colors of $\gamma$ that are present in $\mathcal{Q}$. We note that the
restriction $\gamma|_{\mathcal{Q}}$ of $\gamma$ to $\mathcal{Q}$ is a coloring
of $\mathcal{Q}$. We let $\gamma^{\star}(Q)$ denote the number of points in
$Q$ that are apices of some star of $\mathcal{Q}$ with respect to
$\gamma|_{\mathcal{Q}}$.

For $Q\subseteq P$, let $\mathcal{Q}^{+}$ be the set of all segments of
$\mathcal{P}$ that have no endpoints in $Q$ and cross a segment of
$\mathcal{Q}$. We say that $Q$ is separable with respect to $\gamma$ whenever
$\gamma(e)\notin\gamma(Q)$ for any $e\in\mathcal{Q}^{+}$. If
$\mathcal{Q}^{+}=\emptyset$, then $Q$ is a separable set of $P$. Clearly, if
$Q$ is a separable set of $P$, then $Q$ is separable with respect to any
$\gamma$. For example, each of $A,B,T_{1},T_{2},A\cup B,T_{1}\cup T_{2}$ is a
separable set of $X$.

##  4 Basic facts

Our aim in this section is to prove some basic facts, which we will often use
in the rest of the paper.

Again, in this section $P$ denotes a set of $n\geq 3$ points in general
position in the plane. We recall that if $\gamma$ is a coloring of
$\mathcal{P}$, then $\gamma(P)$ is the set of colors used by $\gamma$ to color
the segments of $\mathcal{P}$.

The next proposition is an immediate consequence of Lovász's theorem, but here
we give an algorithmic proof because we will use the resulting coloring
several times.

######  Proposition 3.

$\chi(D(P))\leq|P|-2.$

###### Proof.

Let $p_{1},p_{2},\ldots,p_{n}$ be any labeling of the points of $P$. Color
each segment of the triangle $\Delta(p_{1},p_{2},p_{3})$ with color $c_{1}$,
and for each $j\in\\{4,5,\ldots,n\\}$ use $c_{j}$ to color each segment in
$\\{p_{j}p_{i}~{}:~{}i=1,2,\ldots,j-1\\}$. Since this defines a proper
coloring of $\mathcal{P}$ with $n-2$ colors, we are done. ∎

Proposition 4 is not used in the rest of the paper, but it is relevant because
illustrates the tightness of Theorem 2, and at the same time the difficulty of
proving it by cumputer search.

######  Proposition 4.

Let
$\mathcal{S}:=\\{t_{1}^{1}t_{2}^{3},b_{1}t_{2}^{3},b_{1}t_{2}^{2},b_{1}t_{2}^{1},b_{1}a_{5},b_{2}a_{5},b_{3}a_{1},b_{3}a_{2},b_{3}a_{3},b_{3}a_{4},b_{3}a_{5},b_{4}a_{1},b_{4}a_{2},b_{4}a_{3},b_{4}a_{4}\\-,b_{4}a_{5},b_{5}t_{1}^{2},b_{5}t_{1}^{1},b_{5}t_{2}^{1},b_{5}a_{1}\\}$.
For $x_{1}x_{2}\in\mathcal{X}\setminus\mathcal{S}$, there are many ways to
color $D(X)$ with 14 colors in which the color of $x_{1}x_{2}$ is not assigned
to any other segment of $\mathcal{X}$.

###### Proof.

Let $x_{1}x_{2}\in\mathcal{X}\setminus\mathcal{S}$. It is not hard to see that
$x_{1}x_{2}$ is a side (no diagonal) of some convex $5$-gon $X_{5}\subset X$.
Similarly, it is easy to find a valid $3$-coloring $\gamma^{\prime}$ of the 10
segments of $\mathcal{X}_{5}$ in such a way that the color
$\gamma^{\prime}(x_{1}x_{2})$ does not appear in any other segment of
$\mathcal{X}_{5}$. In fact, there are exactly 2 ways to do this. Let
$x_{6},x_{7},\ldots,x_{16}$ be any labeling of the points of $X\setminus
X_{5}$. Following the same argument as in the proof of Proposition 3, we can
extend $\gamma^{\prime}$ to a coloring $\gamma$ of $D(X)$ by adding a new star
$S_{i}$ of color $c_{i}$ with apex $x_{i}$ for each $x_{i}\in X\setminus
X_{5}$. ∎

######  Proposition 5.

Let $P^{\prime}$ be a proper subset of $P$, and let $\gamma$ be an optimal
coloring of $D(P)$. Then the following hold:

  * (i)

If $|P^{\prime}|\geq 3$ and $\chi(D(P))=|P|-2$, then
$\chi(D(P^{\prime}))=|P^{\prime}|-2$.

  * (ii)

If $P^{\prime}$ is separable with respect to $\gamma$ and
$|\gamma(P^{\prime})|=|P^{\prime}|,$ then $\chi(D(P))\geq\chi(D(P\setminus
P^{\prime}))+|P^{\prime}|$.

  * (iii)

If $S_{1},\ldots,S_{r}$ are different stars of $\gamma$ with apices
$v_{1},\ldots,v_{r}$, respectively. Then
$\chi(D(P\setminus\\{v_{1},\ldots,v_{r}\\}))=\chi(D(P))-r$.

###### Proof.

By Proposition 3, in order to show $(i)$ it suffices to show that
$\chi(D(P^{\prime}))\geq|P^{\prime}|-2$. Seeking a contradiction, suppose that
there exists a proper coloring $\beta^{\prime}$ of $D(P^{\prime})$ such that
$|\beta^{\prime}(P^{\prime})|<|P^{\prime}|-2$. Then, following the same
argument as in the proof of Proposition 3, we can extend $\beta^{\prime}$ to a
coloring $\beta$ of $D(P)$ by adding a new star $S_{i}$ of color $c_{i}$ with
apex $p_{i}$ for each $p_{i}\in P\setminus P^{\prime}$. Then the number of
colors of $\beta$ is less than $|P^{\prime}|-2+|P\setminus P^{\prime}|=|P|-2$,
contradicting the hypothesis that $\chi(D(P))=|P|-2$.

Let $P^{\prime}$ and $\gamma$ be as in $(ii)$. Since $P^{\prime}$ is a
separable subset of $P$ with respect to $\gamma$, then $\gamma(P^{\prime})$
and $\gamma(P\setminus P^{\prime})$ are disjoint subsets of $\gamma(P)$ and so
$\chi(P)=|\gamma(P)|\geq|\gamma(P\setminus
P^{\prime})|+|\gamma(P^{\prime})|\geq\chi(P\setminus
P^{\prime})+|P^{\prime}|$. This proves $(ii)$.

For $i=1,\ldots,r$, let $S_{i}$ and $v_{i}$ be as in $(iii)$ and let
$Q=P\setminus\\{v_{1},\ldots,v_{r}\\}$. Since the restriction of $\gamma$ to
$D(Q)$ is a coloring of $D(Q)$ with at most $\chi(D(P))-r$ colors, then
$\chi(D(Q))\leq\chi(D(P))-r$. On the other hand, if $\chi(D(Q))<\chi(D(P))-r$
then we can proceed as in the proof of $(i)$ to obtain a coloring $\beta$ of
$D(P)$ with less than $\chi(D(Q))+r$ colors, which is a contradiction. ∎

######  Proposition 6.

Let $\gamma$ be a 4-coloring of $D(C_{5})$. If $\gamma^{\star}(C_{5})=5$, then
$C_{5}$ has two points $p$ and $q$ such that $\\{pq\\}$ is a $2-$star of
$\gamma$ and neither $p$ nor $q$ is an apex of any other star of $\gamma$.

###### Proof.

We start by noting that any chromatic class of $\gamma$ is formed by at most
$5$ segments of $\mathcal{C}_{5}$. From $|\mathcal{C}_{5}|=10$ and the
hypothesis that $\gamma$ has 4 chromatic classes it follows that $\gamma$ has
at most two $2-$stars. On the other hand, since each point of $C_{5}$ is an
apex of a star of $\gamma$, then $\gamma$ must contain at least one $2-$star,
say $S=\\{pq\\}$. We now show that if $S^{\prime}$ is another star of $\gamma$
with apex $v\in\\{p,q\\}$, then $\mathcal{C}_{5}$ has a segment that cannot be
colored by $\gamma$, contradicting the assumption that $\gamma$ is a coloring
of $D(C_{5})$.

Suppose first that $S^{\prime}$ is a $2-$star. Then, $S^{\prime}=\\{vw\\}$ for
some $w\in C_{5}\setminus\\{p,q\\}$. Let $x$ and $y$ be the two points in
$C_{5}\setminus\\{p,q,w\\}$. By hypothesis, for each $z\in\\{x,y\\}$, $\gamma$
has a star $S_{z}$ with apex $z$. As $S$ and $S^{\prime}$ are the only
$2-$stars of $\gamma$, then $S_{x}\neq S_{y}$, and so $S,S^{\prime},S_{x},$
and $S_{y}$ are the 4 chromatic classes of $\gamma$. Since each of them is a
star, then the segment joining the two points in $C_{5}\setminus\\{x,y,v\\}$
cannot be colored by $\gamma$.

Suppose now that $S^{\prime}$ is a star and let $z_{1},z_{2},$ and $z_{3}$ be
the points of $C_{5}\setminus\\{p,q\\}$. Again, for each $z_{i}$ we know that
$\gamma$ has a star $S_{z_{i}}$ with apex $z_{i}$. Since $\gamma$ has exactly
4 chromatic classes, then two of $S_{z_{1}},S_{z_{2}},S_{z_{3}}$ must be the
same. W.l.o.g. we asume $S_{z_{1}}=S_{z_{2}}$. Then $S_{z_{1}}$ must be a
$2-$star, and so $S,S^{\prime},S_{z_{1}},$ and $S_{z_{3}}$ are the 4 chromatic
classes of $\gamma$. Since each of them is a star, then the segment joining
the two points in $C_{5}\setminus\\{v,z_{1},z_{3}\\}$ cannot be colored by
$\gamma$. ∎

######  Proposition 7.

If $\gamma$ is a 3-coloring of $D(C_{5})$, then $\gamma^{\star}(C_{5})\leq 2$.

###### Proof.

Let $v_{1},v_{2},\ldots,v_{5}$ be the points of $C_{5}$, so that they appear
in this cyclic order in $\overline{C_{5}}$. Since each color of $\gamma$ is in
at most two segments of $\overline{C_{5}}$, then the 3 colors
$c_{1},c_{2},c_{3}$ of $\gamma$ appear in $\overline{C_{5}}$. w.l.o.g. assume
that $\gamma(v_{1}v_{2})=c_{1}$, $\gamma(v_{2}v_{3})=\gamma(v_{3}v_{4})=c_{2}$
and $\gamma(v_{4}v_{5})=\gamma(v_{5}v_{1})=c_{3}$.

Suppose first that $v_{1}v_{2}$ is a $2-$star of $\gamma$. Then,
$\gamma(v_{2}v_{4})=c_{2}$ and $\gamma(v_{4}v_{1})=c_{3}$, and so none of
$v_{3},v_{4},v_{5}$ can be an apex of $\gamma$, implying that
$\gamma^{\star}(C_{5})\leq 2$. If $v_{1}v_{2}$ is not a $2-$star of $\gamma$,
then each colour of $\gamma$ appears in at least two segments of
$\mathcal{C}_{5}$, and so each star of $\gamma$ has a unique apex. Since if
the 3 chromatic classes of $\gamma$ are stars, then some of $v_{1}v_{4}$ or
$v_{2}v_{4}$ cannot be colored by $\gamma$, we can assume that $\gamma$ has at
most two stars, and hence $\gamma^{\star}(C_{5})\leq 2$. ∎

######  Theorem 8 (Theorem 1 in [8]).

If $l,k\in{\mathbb{Z}}^{+}$ and $l\geq\max\\{3,k\\}$, then

$\chi(D(C_{k,l}))=k+l-\left\lfloor\sqrt{2l+\frac{1}{4}}-\frac{1}{2}\right\rfloor.$

######  Corollary 9.

Let $\gamma$ be a coloring of $D(X)$. Then

  * ($i$)

$|\gamma(T_{1}\cup T_{2})|\geq 4$.

  * ($ii$)

$|\gamma(A\cup B)|\geq 8$.

  * ($iii$)

$|\gamma(B\cup T_{2})|\geq 6$.

  * ($iv$)

$|\gamma(A\cup T_{1})|\geq 6$.

  * ($v$)

If $|\gamma(T_{1}\cup T_{2})|\geq 6$, then $|\gamma(X)|\geq 14$.

  * ($vi$)

If $|\gamma(A\cup B)|\geq 10$, then $|\gamma(X)|\geq 14$.

###### Proof.

Since $T_{1}\cup T_{2}\sim C_{3,3}$, $A\cup B\sim C_{5,5}$ and $B\cup
T_{2}\sim A\cup T_{1}\sim C_{3,5}$ then $|\gamma(T_{1}\cup T_{2})|\geq 4$,
$|\gamma(A\cup B)|\geq 8$, $|\gamma(B\cup T_{2})|\geq 6$ and $|\gamma(A\cup
T_{1})|\geq 6$, by Theorem 8.

Since $T_{1}\cup T_{2}$ is a separable subset of $X$, then
$|\gamma(X)|\geq|\gamma(A\cup B)|+|\gamma(T_{1}\cup T_{2})|$. If
$|\gamma(T_{1}\cup T_{2})|\geq 6$, then (ii) implies (v). Similarly, if
$|\gamma(A\cup B)|\geq 10$, then (i) implies (vi). ∎

Most of our proofs are by case analysis, depending on the cardinality of the
following sets $\gamma(A),\gamma(B),\gamma(T_{1})$ and $\gamma(T_{2})$. For
the rest of the paper we will use the following additional notation.

  * (N1)

If $|\gamma(A)|=3$, Proposition 7 implies that $A$ has 3 points that are not
apices of $\gamma(A)$. We will denote by $a_{i},a_{j},a_{k}$ these 3 points of
$A$, and w.l.o.g. we assume that $i<j<k$. If $|\gamma(B)|=3$ we define
$b_{p},b_{q},b_{r}$ with $p<q<r$, similarly.

  * (N2)

If $|\gamma(A)|=4$ and $\gamma^{\star}(A)=5$, Proposition 6 implies that $A$
has 2 points defining a $2-$star of $\gamma(A)$ and are such that none of them
is apex of any other star of $\gamma(A)$. We will denote by $a_{i}$ and
$a_{j}$ these 2 points of $A$, and w.l.o.g. we assume that $i<j$. If
$|\gamma(B)|=4$ and $\gamma^{\star}(B)=5$, we define $b_{p}$ and $b_{q}$ with
$p<q$, similarly.

  * (N3)

If $|\gamma(T_{i})|=2$ for $i\in\\{1,2\\}$, we let $e_{i}$ denote the segment
of $T_{i}$ that has a different color than the other two segments of $T_{i}$.

######  Proposition 10.

$\chi(D(A\cup T_{2}))=6$ and $\chi(D(B\cup T_{1}))=6$.

###### Proof.

Since $A\cup T_{2}\sim B\cup T_{1}$, it is enough to show that $\chi(D(B\cup
T_{1}))=6$. Since $\chi(D(B\cup T_{1}))\leq 6$ by Proposition 3, we need to
show that $\chi(D(B\cup T_{1}))\geq 6$. Let $\gamma$ be a coloring of $D(B\cup
T_{1})$. Clearly, $|\gamma(B)|\geq 3$, $|\gamma(T_{1})|\geq 1$ and
$|\gamma(B\cup T_{1})|\geq|\gamma(B)|+|\gamma(T_{1})|$. Then either
$|\gamma(B)|\leq 4$ or we are done.

If $|\gamma(B)|=3$, then $b_{p}t^{1}_{1},b_{q}t^{2}_{1}$ and $b_{r}t^{3}_{1}$
receive distinct color, where $b_{p},b_{q}$ and $b_{r}$ are as in (N1). Since
none of these 3 colors appears in any segment of $\gamma(B)$, we are done.

Suppose now that $|\gamma(B)|=4$. Then $|\gamma(T_{1})|=1$, as otherwise we
are done. If $B$ contains a point $b$ that is not an apex of $\gamma(B)$, then
$\gamma(bt^{1}_{1})$ is the $6$th required color. Then, $\gamma^{\star}(B)=5$
and hence either $\gamma(b_{p}t^{1}_{1})$ or $\gamma(b_{q}t^{3}_{1})$ is the
$6$th required color, where $b_{p}$ and $b_{q}$ are as in (N2). ∎

##  5 Technical claims behind the proof of Theorem 2

As we mentioned before, the bulk of this paper is the proof that

$\chi(D(Q))\geq|Q|-2\mbox{ for any }Q\subseteq X\mbox{ with }|Q|\geq 3.$ (1)

In this section we do this task. As we shall see, the ``symmetry" of $X$ and
the good number of separable subsets that $X$ contains will play a central
role in this task. In particular, in this section we will proof that
Inequality (1) holds for about 15 representative (and strategic) subsets of
$X$ of cardinality at most $11$.

Roughly speaking, our basic proof technique is the following: given $Q\subset
X$, a coloring $\gamma$ of $\mathcal{Q}$, and a nonempty subset
$\\{f_{1},\ldots,f_{m}\\}$ of $\mathcal{Q}$ for which the set of colors
$\\{\gamma(f_{1}),\ldots,\gamma(f_{m})\\}$ is known, we then proceed to find
an ordered sequence $g_{1},\ldots,g_{l}$ of segments in
$\mathcal{Q}\setminus\\{f_{1},\ldots,f_{m}\\}$ such that the number of colors
in
$\\{\gamma(f_{1}),\ldots,\gamma(f_{m})\\}\cup\\{\gamma(g_{1}),\ldots,\gamma(g_{l})\\}$
is equal to $|Q|-2$. We emphasize that for each $i\in\\{1,\ldots,l\\}$, the
determination of the unknown color $\gamma(g_{i})$ depends on the colors
previously fixed, namely

$\\{\gamma(f_{1}),\ldots,\gamma(f_{m})\\}\cup\\{\gamma(g_{1}),\ldots,\gamma(g_{i-1})\\}.$

######  Note 2.

When we have already fixed $|Q|-3$ colors in this process, and so it remains
to prove the needed of the last color, we often write $\gamma(g_{j})\circeq c$
to mean that $\gamma(g_{j})$ must be equal to the color $c$, as otherwise
$\gamma(g_{j})$ is precisely the last required color.

######  Lemma 11.

If $Q$ is a subset of $T_{1}\cup I\cup T_{2}$ with $I\in\\{A,B\\}$ and
$|Q|\geq 3$, then $\chi(D(Q))=|Q|-2$.

###### Proof.

By Proposition 5 ($i$), it is enough to show the assertion for $Q=T_{1}\cup
I\cup T_{2}$. By Proposition 3, all we need to show is that $\chi(D(Q))\geq
9$. We only discuss the case $I=A$. The case $I=B$ can be handled in a similar
way. Thus we assume $Q=T_{1}\cup A\cup T_{2}$.

Let $\gamma$ be an optimal coloring of $D(Q)$. Since $|\gamma(A)|\geq 3$, then
we can assume $|\gamma(T_{1}\cup T_{2})|\in\\{4,5\\}$, as otherwise we are
done. Similarly, since $|\gamma(Q)|\geq|\gamma(A)|+|\gamma(T_{1}\cup T_{2})|$,
then $|\gamma(A)|\in\\{3,4\\}$.

We claim that if $|\gamma(T_{i})|\geq 3$ for some $i\in\\{1,2\\}$, then
$\chi(D(Q))\geq 9$. Indeed, since $T_{i}$ is a separable subset of $Q$ with
respect to $\gamma$, then $|\gamma(D(Q))|\geq|\gamma(D(Q\setminus
T_{i}))|+|\gamma(D(T_{i}))|\geq|\gamma(D(Q\setminus T_{i}))|+3$ by Proposition
5 $(ii)$. Since $|\gamma(D(Q\setminus T_{i}))|\geq 6$ by Theorem 8, if $i=2$
(respectively, Proposition 10 if $i=1$). Then we may assume that
$1\leq|\gamma(T_{1})|,|\gamma(T_{2})|\leq 2$.

Case 1. Suppose that $|\gamma(A)|=3$. Let $a_{i},a_{j},a_{k}\in A$ be as in
(N1).

(1.1) If $|\gamma(T_{1})|=1=|\gamma(T_{2})|$, then $|\gamma(T_{1}\cup
T_{2})|=5$ and one of $a_{i}t^{1}_{1}$ or $a_{j}t^{1}_{2}$ provides the 9th
color.

(1.2) If $|\gamma(T_{1})|=1$ and $|\gamma(T_{2})|=2$, then none of
$\gamma(a_{i}t^{1}_{1}),\gamma(a_{j}t^{2}_{1}),$ and $\gamma(a_{k}t^{3}_{1})$
belongs to $\gamma(A)\cup\gamma(T_{1})$, and so $|\gamma(A\cup T_{1})|\geq 7$.
This inequality together with $|\gamma(T_{2})|=2$ imply the required
inequality.

(1.3) If $|\gamma(T_{1})|=2$ and $|\gamma(T_{2})|=1$, then either
$l(e_{1})a_{i}$ or $r(e_{1})t^{2}_{2}$ provides the $7$th color, where $e_{1}$
is as in (N3). The last two required colors are $\gamma(t^{1}_{2}a_{j})$ and
$\gamma(t^{3}_{2}a_{k})$.

(1.4) Suppose that $|\gamma(T_{1})|=2=|\gamma(T_{2})|$. We need to show the
existence of 2 additional colors. Let $e_{1}$ and $e_{2}$ be as in (N3), let
$f_{1}:=l(e_{1})l(e_{2})$ and $f_{2}:=r(e_{1})r(e_{2})$. We assume w.l.o.g.
that
$\gamma(T_{1})=\\{c_{4},c_{5}\\},\gamma(T_{2})=\\{c_{6},c_{7}\\},\gamma(e_{1})=c_{4}$
and $\gamma(e_{2})=c_{7}$.

We note that if $\gamma(h)\notin\gamma(T_{2})$ for some $h\in a_{k}*T_{2}$,
then $h$ and either $l(e_{1}){a_{i}}$ or $r(e_{1}){a_{j}}$ provide the
required two colors. Then the color of any segment in $a_{k}*T_{2}$ must be
$c_{6}$ or $c_{7}$. For $l\in\\{1,2,3\\}$, let $h_{l}=a_{k}t^{l}_{2}$.

$\bullet$ Suppose that $e_{2}=t^{1}_{2}t^{2}_{2}$. Then
$\gamma(t^{1}_{2}t^{3}_{2})=\gamma(t^{2}_{2}t^{3}_{2})=c_{6}$,
$\gamma(h_{3})\circeq c_{6}$ and $\gamma(h_{1})\circeq c_{7}$. Suppose first
that $\gamma(h_{2})=c_{7}$. If $\gamma(f_{2})\neq c_{4}$, then $f_{2}$ and
$t^{1}_{2}a_{j}$ provide the required colors. Then $\gamma(f_{2})=c_{4}$, and
$f_{1}$ together with either $l(f_{1}){a_{i}}$ or $r(f_{1}){a_{j}}$ provide
the required colors. Suppose now that $\gamma(h_{2})=c_{6}$. We note that
$\gamma(t^{1}_{2}a_{i})$ and $\gamma(t^{2}_{2}a_{j})$ cannot be $c_{6}$, and
moreover, exactly one of them must be $c_{7}$ as otherwise we are done. Since
if $\gamma(t^{1}_{2}a_{i})=c_{7}$, then $t^{2}_{2}a_{j}$ together with either
$l(e_{1}){a_{i}}$ or $r(e_{1})t^{3}_{2}$ provide the two required colors. Then
$\gamma(t^{2}_{2}a_{j})=c_{7}$, and so $t^{1}_{2}a_{i}$ together with either
$l(e_{1}){t^{2}_{2}}$ or $r(e_{1}){t^{3}_{2}}$ provide the two required
colors.

$\bullet$ Suppose that $e_{2}=t^{2}_{2}t^{3}_{2}$. Then
$\gamma(t^{1}_{2}t^{2}_{2})=\gamma(t^{1}_{2}t^{3}_{2})=c_{6}$,
$\gamma(h_{1})=c_{6}$ and $\gamma(h_{3})=c_{7}$. We note that neither
$\gamma(t^{1}_{2}a_{i})$ nor $\gamma(t^{2}_{2}a_{j})$ can be $c_{7}$, and
moreover, exactly one of them must be $c_{6}$ as otherwise we are done.
Suppose first that $\gamma(t^{1}_{2}a_{i})=c_{6}$. Then $\gamma(h_{2})\circeq
c_{7}$, and so $t^{2}_{2}a_{j}$ together with either $l(e_{1})a_{i}$ or
$r(e_{1})t^{3}_{2}$ provide the two required colors. Suppose now that
$\gamma(t^{2}_{2}a_{j})=c_{6}$. Note that if $\gamma(h_{2})=c_{6}$, then
$t^{1}_{2}a_{j}$ together with either $l(e_{1})a_{i}$ or $r(e_{1})t^{2}_{2}$
provide the two required colors. Then $\gamma(h_{2})=c_{7}$, and hence
$t^{1}_{2}a_{i}$ and some of $f_{1}$ or $f_{2}$ give the two required colors.

$\bullet$ Suppose that $e_{2}=t^{1}_{2}t^{3}_{2}$. Then
$\gamma(t^{1}_{2}t^{2}_{2})=\gamma(t^{2}_{2}t^{3}_{2})=c_{6}$,
$\gamma(h_{1})=c_{7}$ and $\gamma(h_{3})=c_{7}$. The required colors are given
by $t^{1}_{2}a_{j}$ and some segment of $l(e_{1})a_{i}$ or
$r(e_{1})t^{3}_{2}$.

Case 2. Suppose that $|\gamma(A)|=4$. Since
$|\gamma(T_{1})|=1=|\gamma(T_{2})|$ imply $|\gamma(T_{1}\cup T_{2})|\geq 5$,
and we know that $|\gamma(A\cup T_{1}\cup
T_{2})|\geq|\gamma(A)|+|\gamma(T_{1}\cup T_{2})|$, we can assume that some of
$|\gamma(T_{1})|\geq 2$ or $|\gamma(T_{2})|\geq 2$ holds.

(2.1) Suppose $\gamma^{\star}(A)<5$. Let $a$ be a point of $A$ that is not an
apex of $\gamma(A)$.

$\bullet$ If $|\gamma(T_{1})|=2$ and $|\gamma(T_{2})|=1$, then $at^{3}_{2}$
together with either $l(e_{1})t^{1}_{2}$ or $r(e_{1})t^{2}_{2}$ give the two
required colors.

$\bullet$ If $|\gamma(T_{1})|=1$ and $|\gamma(T_{2})|=2$, then $at^{1}_{1}$
together with either $t_{1}^{2}l(e_{2})$ or $t_{1}^{3}r(e_{2})$ give the two
required colors.

$\bullet$ Suppose that $|\gamma(T_{1})|=2=|\gamma(T_{2})|$. Then we need to
show the existence of one additional color. Let $f_{1}:=l(e_{1})l(e_{2})$ and
$f_{2}:=r(e_{1})r(e_{2})$. We note that
$\\{\gamma(f_{1}),\gamma(f_{2})\\}=\\{\gamma(e_{1}),\gamma(e_{2})\\}$ as
otherwise we are done. Then $\gamma(f_{1})\neq\gamma(e_{i})$ for some
$i\in\\{1,2\\}$. Let $v:=f_{1}\cap e_{i}$. Then
$v\in\\{t_{1}^{1},t_{1}^{2},t_{2}^{1},t_{2}^{2}\\}$. Since $v\neq t_{2}^{2}$
implies that $\gamma(av)$ is the required color, we can assume $v=t_{2}^{2}$
and hence we must have $e_{i}=t_{2}^{2}t_{2}^{3}$. Then
$\gamma(t_{2}^{2}r(e_{1}))\in\\{\gamma(f_{1}),\gamma(f_{2})\\}$ as otherwise
we are done. If $\gamma(t_{2}^{2}r(e_{1}))=\gamma(f_{1})$ (respectively,
$\gamma(t_{2}^{2}r(e_{1}))=\gamma(f_{2})$), then $\gamma(l(e_{1})a)$
(respectively, $\gamma(t_{2}^{3}a)$) is the required color.

(2.2) Suppose that $\gamma^{\star}(A)=5$. Let $a_{i}$ and $a_{j}$ be as in
(N2).

$(2.2.1)$ Suppose that $|\gamma(T_{1})|=2$ and $|\gamma(T_{2})|=1$. Clearly,
$\gamma(t^{1}_{2}a_{i}),\gamma(t^{3}_{2}a_{j})\notin\gamma(T_{2})$, and
moreover, exactly one of these two must be $\gamma(a_{i}a_{j})$ as otherwise
we are done. If $\gamma(t^{1}_{2}a_{i})=\gamma(a_{i}a_{j})$, then
$t^{3}_{2}a_{j}$ together with either $l(e_{1})t^{1}_{2}$ or
$r(e_{1})t^{2}_{2}$ give the two required colors. Then
$\gamma(t^{3}_{2}a_{j})=\gamma(a_{i}a_{j})$, and so $t^{1}_{2}a_{i}$ together
with either $l(e_{1})t^{2}_{2}$ or $r(e_{1})t^{3}_{2}$ give the two required
colors.

$(2.2.2)$ Suppose that $|\gamma(T_{1})|=1$ and $|\gamma(T_{2})|=2$. We need to
show the existence of two additional colors. Assume w.l.o.g. that
$\gamma(T_{2})=\\{c_{6},c_{7}\\}$ and that $\gamma(e_{2})=c_{7}$.

$\bullet$ Suppose that $e_{2}=t^{2}_{2}t^{3}_{2}$. Then
$\gamma(t^{1}_{2}t^{2}_{2})=\gamma(t^{1}_{2}t^{3}_{2})=c_{6}$. Clearly, either
$\gamma(t^{2}_{1}t^{2}_{2})$ or $\gamma(t^{3}_{1}t^{3}_{2})$ is the $8$th
color $c_{8}$ and the other one must be $c_{7}$, as otherwise we are done. If
$\gamma(t^{2}_{1}t^{2}_{2})=c_{7}$ and $\gamma(t^{3}_{1}t^{3}_{2})=c_{8}$,
then either $a_{i}t_{1}^{1}$ or $a_{j}t_{1}^{2}$ provides the $9$th color, and
if $\gamma(t^{3}_{1}t^{3}_{2})=c_{7}$ and $\gamma(t^{2}_{1}t^{2}_{2})=c_{8}$,
then
$\gamma(t^{1}_{1}a_{i})\circeq\gamma(a_{i}a_{j}),~{}\gamma(t^{2}_{1}a_{j})\circeq
c_{8}$ and $\gamma(t^{3}_{1}t^{2}_{2})\circeq c_{7}$. These imply that
$\gamma(t^{3}_{2}a_{j})$ is the $9$th color.

$\bullet$ Suppose that $e_{2}=t^{1}_{2}t^{2}_{2}$. Then
$\gamma(t^{1}_{2}t^{3}_{2})=\gamma(t^{2}_{2}t^{3}_{2})=c_{6}$. Clearly, either
$\gamma(t^{2}_{1}t^{1}_{2})$ or $\gamma(t^{3}_{1}t^{2}_{2})$ is the $8$th
color $c_{8}$ and the other one must be $c_{7}$, as otherwise we are done.
Then $\gamma(t^{1}_{1}a_{i})\circeq\gamma(a_{i}a_{j})$. If
$\gamma(t^{2}_{1}t^{1}_{2})=c_{7}$ and $\gamma(t^{3}_{1}t^{2}_{2})=c_{8}$,
then $\gamma(t^{2}_{1}a_{j})$ is the $9$th color. Suppose now that
$\gamma(t^{3}_{1}t^{2}_{2})=c_{7}$ and $\gamma(t^{2}_{1}t^{1}_{2})=c_{8}$.
Then $\gamma(t^{2}_{1}a_{j})\circeq c_{8},~{}\gamma(t^{3}_{1}t^{1}_{2})\circeq
c_{7}$ and $\gamma(t^{3}_{1}t^{3}_{2})\circeq c_{6}$. These imply that
$\gamma(t^{2}_{2}a_{j})$ is the $9$th color.

$\bullet$ Suppose that $e_{2}=t^{1}_{2}t^{3}_{2}$. Then
$\gamma(t^{1}_{2}t^{2}_{2})=\gamma(t^{2}_{2}t^{3}_{2})=c_{6}$. Clearly, either
$\gamma(t^{2}_{1}t^{1}_{2})$ or $\gamma(t^{3}_{1}t^{3}_{2})$ is the $8$th
color $c_{8}$ and the other one must be $c_{7}$, as otherwise we are done.
Then $\gamma(t^{1}_{1}a_{i})\circeq\gamma(a_{i}a_{j})$. If
$\gamma(t^{2}_{1}t^{1}_{2})=c_{7}$ and $\gamma(t^{3}_{1}t^{3}_{2})=c_{8}$,
then $\gamma(t^{2}_{1}a_{j})$ is the $9$th color. Suppose now that
$\gamma(t^{3}_{1}t^{3}_{2})=c_{7}$ and $\gamma(t^{2}_{1}t^{1}_{2})=c_{8}$,
then $\gamma(t^{2}_{1}a_{j})\circeq c_{8}$ and
$\gamma(t^{3}_{1}t^{1}_{2})\circeq c_{7}$. These imply that
$\gamma(t^{3}_{2}a_{j})$ is the $9$th color.

$(2.2.3)$ Suppose that $|\gamma(T_{1})|=2=|\gamma(T_{2})|$. As above, let
$f_{1}:=l(e_{1})l(e_{2})$ and $f_{2}:=r(e_{1})r(e_{2})$. We need to show the
existence of one additional color, say $c_{9}$. Since if $|\gamma(T_{1}\cup
T_{2})|\geq 5$ there is nothing to prove, we assume $|\gamma(T_{1}\cup
T_{2})|=4$. Suppose that
$\gamma(T_{1})=\\{c_{4},c_{5}\\},\gamma(T_{2})=\\{c_{6},c_{7}\\},\gamma(e_{1})=c_{4}$
and $\gamma(e_{2})=c_{7}$. Then either
$\\{\gamma(f_{1}),\gamma(f_{2})\\}=\\{c_{4},c_{7}\\}$ or we are done. Let
$u_{1}:=l(e_{1})$ and $u_{2}:=r(e_{1})$.

$\bullet$ Suppose that $e_{2}=t^{1}_{2}t^{3}_{2}$. Then
$\gamma(t^{1}_{2}t^{2}_{2})=\gamma(t^{2}_{2}t^{3}_{2})=c_{6}$. If
$\gamma(f_{1})=c_{7}$ and $\gamma(f_{2})=c_{4}$, then either $u_{1}a_{i}$ or
$t_{2}^{3}a_{j}$ must be colored with $c_{9}$. Suppose now that
$\gamma(f_{1})=c_{4}$ and $\gamma(f_{2})=c_{7}$. Then either
$\gamma(u_{2}t^{1}_{2})\in\\{c_{4},c_{7}\\}$ or $\gamma(u_{2}t^{1}_{2})$ is
the $9$th color. If $\gamma(u_{2}t^{1}_{2})=c_{4}$, then either $u_{1}a_{i}$
or $t_{2}^{1}a_{j}$ must be colored with $c_{9}$, and if
$\gamma(u_{2}t^{1}_{2})=c_{7}$, then either $a_{i}t_{2}^{1}$ or
$a_{j}t_{2}^{3}$ must be colored with $c_{9}$.

$\bullet$ Suppose that $e_{2}=t^{1}_{2}t^{2}_{2}$. Then
$\gamma(t^{1}_{2}t^{3}_{2})=\gamma(t^{2}_{2}t^{3}_{2})=c_{6}$. If
$\gamma(f_{1})=c_{7}$ and $\gamma(f_{2})=c_{4}$, then either
$\gamma(u_{1}t^{2}_{2})\in\\{c_{4},c_{7}\\}$ or we are done. If
$\gamma(u_{1}t^{2}_{2})=c_{7}$ then either $u_{1}a_{i}$ or $t_{2}^{1}a_{j}$
must be colored with $c_{9}$, and if $\gamma(u_{1}t^{2}_{2})=c_{4}$ then
$\gamma(u_{1}a_{i})\circeq\gamma(a_{i}a_{j})$ and either $t_{2}^{2}a_{j}$ or
$t_{2}^{3}u_{2}$ is colored with $c_{9}$. Suppose now that
$\gamma(f_{1})=c_{4}$ and $\gamma(f_{2})=c_{7}$. Then either
$\gamma(u_{2}t^{1}_{2})\in\\{c_{4},c_{7}\\}$ or we are done. If
$\gamma(u_{2}t^{1}_{2})=c_{4}$ then either $u_{1}a_{i}$ or $t^{1}_{2}a_{j}$
must be colored with $c_{9}$, and if $\gamma(u_{2}t^{1}_{2})=c_{7}$, then
$\gamma(a_{i}t^{1}_{2})\circeq\gamma(a_{i}a_{j}),\gamma(a_{j}t^{2}_{2})\circeq
c_{6}$, and so $\gamma(u_{2}t^{3}_{2})=c_{9}$.

$\bullet$ Suppose that $e_{2}=t^{2}_{2}t^{3}_{2}$. Then
$\gamma(t^{1}_{2}t^{2}_{2})=\gamma(t^{1}_{2}t^{3}_{2})=c_{6}$. If
$\gamma(f_{1})=c_{7}$ and $\gamma(f_{2})=c_{4}$, then either $u_{1}a_{i}$ or
$t^{3}_{2}a_{j}$ must be colored with $c_{9}$. Suppose now that that
$\gamma(f_{1})=c_{4}$ and $\gamma(f_{2})=c_{7}$. Then either
$\gamma(u_{2}t^{2}_{2})\in\\{c_{4},c_{7}\\}$ or we are done. If
$\gamma(u_{2}t^{2}_{2})=c_{4}$, then
$\gamma(u_{1}a_{i})\circeq\gamma(a_{i}a_{j}),\gamma(t^{2}_{2}a_{j})\circeq
c_{6}$, and so $\gamma(u_{1}t^{1}_{2})=c_{9}$. If
$\gamma(u_{2}t^{2}_{2})=c_{7}$, then
$\gamma(t^{3}_{2}a_{j})\circeq\gamma(a_{i}a_{j}),\gamma(t^{2}_{2}a_{i})\circeq
c_{6},\gamma(u_{2}t^{1}_{2})\circeq c_{4}$, and so $\gamma(u_{1}a_{i})=c_{9}$.
∎

######  Corollary 12.

Let $\gamma$ be a coloring of $D(X)$. If $I\in\\{A,B\\}$ and $|\gamma(I)|\geq
5$ then $|\gamma(D(X))|\geq 14$.

###### Proof.

Since $I$ is a separable subset of $X$, then Lemma 11 imply
$|\gamma(D(X))|\geq|\gamma(X\setminus I)|+|\gamma(I)|\geq 9+5$. ∎

######  Lemma 13.

Let $A^{\prime}\subset A,B^{\prime}\subset B$ and $T^{\prime}\subset(T_{1}\cup
T_{2})$ be such that $|A^{\prime}|=|B^{\prime}|=|T^{\prime}|=3$. If $Q$ is a
subset of $A^{\prime}\cup T^{\prime}\cup B^{\prime}$ with $|Q|\geq 3$, then
$\chi(D(Q))=|Q|-2$.

###### Proof.

By Proposition 5($i$), it is enough to show the assertion for
$Q:=A^{\prime}\cup T^{\prime}\cup B^{\prime}$. By Proposition 3, all we need
to show is that $\chi(D(Q))\geq 7$. On the other hand, it is not hard see that
if $T^{\prime}$ is concave up (respectively, concave down) then $Q\sim
A^{\prime}\cup T_{2}\cup B^{\prime}$ (respectively, $Q\sim A^{\prime}\cup
T_{1}\cup B^{\prime}$). Then, w.l.o.g. we can assume that $Q$ is either
$A^{\prime}\cup T_{1}\cup B^{\prime}$ or $A^{\prime}\cup T_{2}\cup
B^{\prime}$. We only analyze the case $T^{\prime}=T_{1}$. The case
$T^{\prime}=T_{2}$ can be handled in a similar way.

Let $\gamma$ be a coloring of $D(Q)$. Clearly, each of $A^{\prime},B^{\prime}$
and $T_{1}$ is a separable subset of $Q$. Since $|\gamma(T_{1}\cup
B^{\prime})|\geq 4$ by Lemma 11, we can assume $1\leq|\gamma(A^{\prime})|\leq
2$, as otherwise we are done. Similarly, from $(A^{\prime}\cup B^{\prime})\sim
C_{3,3}\sim(A^{\prime}\cup T_{1})$ and $|\gamma(C_{3,3})|\geq 4$ (by Theorem
8), we can conclude that $1\leq|\gamma(T_{1})|,|\gamma(B^{\prime})|\leq 2$.
Let $a_{i},a_{j},a_{k}$ (resp. $b_{p},b_{q},b_{r}$) be the points of
$A^{\prime}$ (respectively, $B^{\prime}$) with $i<j<k$ (resp. $p<q<r$).

Case 1. Suppose that $|\gamma(T_{1})|=1$.

$(1.1)$ Suppose that $|\gamma(A^{\prime})|=1$. Then, $\gamma$ assigns distinct
colors to $a_{i}t^{1}_{1},$ $a_{j}t^{2}_{1},$ and $a_{k}t^{3}_{1}$ and hence
$|\gamma(A^{\prime}\cup T_{1})|\geq 5$. Since $|\gamma(B^{\prime})|\geq 2$
implies the required inequality, we can assume that $|\gamma(B^{\prime})|=1$.
Then either $a_{i}b_{p}$ or $t^{1}_{1}b_{q}$ provides the 7th color.

$(1.2)$ Suppose that $|\gamma(A^{\prime})|=2$ and $|\gamma(B^{\prime})|=1$.
Let $a^{\prime}$ be the segment of $A^{\prime}$ that has a different color
than the other two segments of $A^{\prime}$. Since $|\gamma(T_{1})|=1$, we
need to show the existence of 3 additional colors. Clearly,
$c_{1}:=\gamma(b_{p}t^{1}_{1})$ and $c_{2}:=\gamma(b_{r}t_{1}^{3})$ are 2 new
colors. Then $\gamma(t_{1}^{1}b_{q})\circeq c_{1}$ and so either
$l(a^{\prime})b_{p}$ or $r(a^{\prime})t_{1}^{2}$ provides the 7th color.

$(1.3)$ Suppose that $|\gamma(A^{\prime})|=2$ and $|\gamma(B^{\prime})|=2$.
Let $a^{\prime}$ (resp. $b^{\prime}$) be the segment of $A^{\prime}$ (resp.
$B^{\prime}$) that has a different color than the other two segments of
$A^{\prime}$ (resp. $B^{\prime}$). Since $|\gamma(T_{1})|=1$, we need to show
the existence of 2 additional colors, say $c_{6}$ and $c_{7}$. Clearly, a
segment of $l(b^{\prime})t_{1}^{1}$ or $r(b^{\prime})t_{1}^{3}$ provides the
$6$th color $c_{6}$ and the other one must be colored with
$\gamma(b^{\prime})$, as otherwise we are done. If
$\gamma(l(b^{\prime})t_{1}^{1})=c_{6}$ then either $l(a^{\prime})t_{1}^{2}$ or
$r(a^{\prime})t_{1}^{3}$ is colored with $c_{7}$. If
$\gamma(r(b^{\prime})t_{1}^{3})=c_{6}$ then either $l(a^{\prime})t_{1}^{1}$ or
$r(a^{\prime})t_{1}^{2}$ is colored with $c_{7}$.

Case 2. Suppose that $|\gamma(T_{1})|=2$. Let $e_{1}$ be as in (N3). Suppose
that $\gamma(T_{1})=\\{c_{1},c_{3}\\}$ and that $\gamma(e_{1})=c_{1}$.

$(2.1)$ Suppose that $|\gamma(A^{\prime})|=1$. If $|\gamma(B^{\prime})|=1$
then $|\gamma(A^{\prime}\cup B^{\prime})|\geq 5$, and so $|\gamma(Q)|\geq 7$,
as required. Thus, we can assume that $|\gamma(B^{\prime})|=2$. Let
$b^{\prime}$ be the segment of $B^{\prime}$ that has a different color than
the other two segments of $B^{\prime}$. Then, we need to show the existence of
2 additional colors, say $c_{6}$ and $c_{7}$.

Clearly, a segment in $\\{a_{i}l(b^{\prime}),a_{k}r(b^{\prime})\\}$ is colored
with the $6$th color $c_{6}$ and the other one must be colored with
$\gamma(b^{\prime})$, as otherwise we are done. Let $[]$ be the quadrilateral
formed by $a_{i},a_{k},l(b^{\prime})$ and $r(b^{\prime})$.

Suppose that $\gamma(a_{i}l(b^{\prime}))=c_{6}$ and
$\gamma(a_{k}r(b^{\prime}))=\gamma(b^{\prime})$. If $T_{1}$ is not on the left
of $[]$, then either $l(e_{1})a_{j}$ or $r(e_{1})a_{k}$ provides the 7th
color.

Thus we can assume that $T_{1}$ lies on the left of $[]$. Then
$\gamma(a_{j}l(b^{\prime}))\circeq c_{6}$, $\gamma(l(e_{1})a_{i})\circeq
c_{1}$, $\gamma(r(e_{1})a_{i})\circeq c_{1}$ and $\gamma(r(e_{1})a_{j})\circeq
c_{6}$. Then either $a_{i}t_{1}^{m}$ or $l(e_{1})l(b^{\prime})$ provides the
7th color, where $t_{1}^{m}$ is the point in $T_{1}$ but not in $e_{1}$.

Suppose now that $\gamma(a_{i}l(b^{\prime}))=\gamma(b^{\prime})$ and
$\gamma(a_{k}r(b^{\prime}))=c_{6}$. If $T_{1}$ is not on the right of $[]$,
then either $\gamma(l(e_{1})a_{i})$ or $\gamma(r(e_{1})a_{j})$ provides the
7th color. Thus we can assume that $T_{1}$ lies on the right of $[]$. Then
$\\{\gamma(l(e_{1})a_{j}),\gamma(r(e_{1})a_{k})\\}=\\{c_{1},c_{6}\\}$, as
otherwise we are done.

$\bullet$ If $\gamma(l(e_{1})a_{j})=c_{1}$ and $\gamma(r(e_{1})a_{k})=c_{6}$,
then $a_{j}r(b^{\prime})$ provides the 7th color.

$\bullet$ If $\gamma(l(e_{1})a_{j})=c_{6}$ and $\gamma(r(e_{1})a_{k})=c_{1}$,
then $\gamma(a_{j}r(b^{\prime}))\circeq c_{6}$ and
$\gamma(l(e_{1})a_{k})\circeq c_{1}$. If $t_{1}^{3}\in e_{1}$, then
$t_{1}^{3}r(b^{\prime})$ provides the 7th color. If $t_{1}^{3}\notin e_{1}$,
then $e_{1}=t_{1}^{1}t_{1}^{2}$ and $\gamma(t_{1}^{1}r(b^{\prime}))\circeq
c_{6}$, and either $t_{1}^{2}r(b^{\prime})$ or $t_{1}^{3}a_{k}$ provides the
7th color.

$(2.2)$ Suppose that $|\gamma(A^{\prime})|=2$ and $|\gamma(B^{\prime})|=1$.
Let $a^{\prime}$ be the segment of $A^{\prime}$ that has a different color
than the other two segments of $A^{\prime}$. We need to show the existence of
2 additional colors, say $c_{6}$ and $c_{7}$. Clearly, a segment in
$\\{l(a^{\prime})b_{p},r(a^{\prime})b_{r}\\}$ is colored with the $6$th color
$c_{6}$ and the other one must be colored with $\gamma(a^{\prime})$, as
otherwise we are done. Let $[]$ be the quadrilateral formed by
$b_{p},b_{r},l(a^{\prime})$ and $r(a^{\prime})$.

Suppose that $\gamma(l(a^{\prime})b_{p})=\gamma(a^{\prime})$ and
$\gamma(r(a^{\prime})b_{r})=c_{6}$. Suppose first that $T_{1}$ lies inside of
$[]$.

$\bullet$ If $e_{1}=t_{1}^{1}t_{1}^{2}$, then $\gamma(t_{1}^{1}b_{p})\circeq
c_{1}$ and $\gamma(r(a^{\prime})t_{1}^{2})\circeq c_{6}$. Then either
$b_{q}t_{1}^{2}$ or $b_{r}t_{1}^{3}$ is colored with $c_{7}$.

$\bullet$ If $e_{1}=t_{1}^{1}t_{1}^{3}$, then $\gamma(t_{1}^{1}b_{q})\circeq
c_{1}$. Then either $b_{p}t_{1}^{1}$ or $b_{q}t_{1}^{3}$ is colored with
$c_{7}$.

$\bullet$ If $e_{1}=t_{1}^{2}t_{1}^{3}$, then $\gamma(t_{1}^{3}b_{q})\circeq
c_{1},\gamma(r(a^{\prime})t_{1}^{2})\circeq c_{6}$ and
$\gamma(t_{1}^{1}b_{p})\circeq c_{3}$. Then either $b_{q}t_{1}^{2}$ or
$b_{r}t_{1}^{3}$ is colored with $c_{7}$.

Suppose now that $T_{1}$ lies in the exterior of $[]$. Then $T_{1}$ lies on
the right of $[]$ and $\gamma(r(a^{\prime})b_{q})\circeq c_{6}$.

$\bullet$ If $e_{1}=t_{1}^{1}t_{1}^{2}$, then $\gamma(b_{r}t_{1}^{1})\circeq
c_{1}$ and $\gamma(b_{r}t_{1}^{3})\circeq c_{3}$. Then
$\gamma(b_{r}t_{1}^{2})\in\\{c_{1},c_{3}\\}$ or we are done. If
$\gamma(b_{r}t_{1}^{2})=c_{1}$, then either $r(a^{\prime})t_{1}^{2}$ or
$b_{q}t_{1}^{1}$ must be colored with $c_{7}$. If
$\gamma(b_{r}t_{1}^{2})=c_{3}$, then $\gamma(r(a^{\prime})t_{1}^{2})\circeq
c_{6},\gamma(r(a^{\prime})t_{1}^{3})\circeq
c_{6},\gamma(b_{q}t_{1}^{2})\circeq c_{1}$ and so $b_{p}t_{1}^{1}$ must be
colored with $c_{7}$.

$\bullet$ If $e_{1}=t_{1}^{1}t_{1}^{3}$, then $\gamma(t_{1}^{1}b_{r})\circeq
c_{1}$ and $\gamma(t_{1}^{3}b_{r})\circeq c_{1}$. Then either $b_{p}t_{1}^{1}$
or $r(a^{\prime})t_{1}^{3}$ is colored with $c_{7}$.

$\bullet$ If $e_{1}=t_{1}^{2}t_{1}^{3}$, then $\gamma(t_{1}^{3}b_{r})\circeq
c_{1}$, $\gamma(r(a^{\prime})t_{1}^{2})\circeq
c_{6},\gamma(t_{1}^{1}b_{p})\circeq c_{3}$ and $\gamma(t_{1}^{2}b_{r})\circeq
c_{1}$. Then either $r(a^{\prime})t_{1}^{3}$ or $b_{q}t_{1}^{2}$ is colored
with $c_{7}$.

Suppose now that $\gamma(l(a^{\prime})b_{p})=c_{6}$ and
$\gamma(r(a^{\prime})b_{r})=\gamma(a^{\prime})$.

$\bullet$ If $e_{1}=t_{1}^{1}t_{1}^{2}$, then $\gamma(t_{1}^{3}b_{r})\circeq
c_{3},\gamma(t_{1}^{1}b_{q})\circeq c_{1},\gamma(t_{1}^{2}b_{q})\circeq
c_{1},\gamma(t_{1}^{2}b_{r})\circeq c_{3}$ and
$\gamma(t_{1}^{3}r(a^{\prime}))\circeq\gamma(a^{\prime})$. These imply that
either $t_{1}^{2}l(a^{\prime})$ or $t_{1}^{1}b_{p}$ must be colored with
$c_{7}$.

$\bullet$ If $e_{1}=t_{1}^{1}t_{1}^{3}$, then either $t_{1}^{1}b_{q}$ or
$t_{1}^{3}b_{r}$ is colored with $c_{7}$.

$\bullet$ If $e_{1}=t_{1}^{2}t_{1}^{3}$, then $\gamma(t_{1}^{3}b_{r})\circeq
c_{1},\gamma(t_{1}^{1}b_{q})\circeq c_{3},\gamma(t_{1}^{2}b_{q})\circeq
c_{3},\gamma(t_{1}^{2}b_{r})\circeq c_{1}$ and
$\gamma(t_{1}^{3}r(a^{\prime}))\circeq\gamma(a^{\prime})$. These imply that
either $t_{1}^{1}b_{p}$ or $t_{1}^{2}l(a^{\prime})$ is colored with $c_{7}$.

$(2.3)$ Suppose that $|\gamma(A^{\prime})|=2$ and $|\gamma(B^{\prime})|=2$.
Since $|\gamma(T_{1})|=2$, we need to show the existence of 1 additional
color. Let $a^{\prime}$ (resp. $b^{\prime}$) be the segments of $A^{\prime}$
(resp. $B^{\prime}$) that has a different color than the other two segments of
$A^{\prime}$ (resp. $B^{\prime}$). We note that
$\\{\gamma(a^{\prime}),\gamma(b^{\prime})\\}=\\{\gamma(l(a^{\prime})l(b^{\prime})),\gamma(r(a^{\prime})r(b^{\prime}))\\}$
as otherwise we are done.

Let $[]$ be the convex quadrilateral formed be the endpoints of $a^{\prime}$
and $b^{\prime}$, and let $x$ (resp. $y$) be the endpoint of $a^{\prime}$
(resp. $b^{\prime}$) that is incident with both colors $\gamma(a^{\prime})$
and $\gamma(b^{\prime})$. Then, either $x=r(a^{\prime})$ or $y=r(b^{\prime})$
holds. Suppse that $T_{1}$ lies in the interior of $[]$. If $t_{1}^{3}\in
e_{1}$, then one of $xl(e_{1})$ or $yt_{1}^{3}$ provides the required color.
If $t_{1}^{3}\notin e_{1}$, then $e_{1}=t_{1}^{1}t_{1}^{2}$ and one of
$xt_{2}^{2}$ or $yt_{1}^{1}$ provides the required color. Thus, we can assume
that $T_{1}$ lies outside of $[]$. Let $t_{1}^{m}$ be the point of $T_{1}$
that does not belong to $e_{1}$.

$\bullet$ Suppose that $x$ is the endpoint of $a^{\prime}$ that is closest to
$t^{2}_{1}$. Then the triangle $\Delta(e_{1},x)$ must be colored with $c_{1}$
and $\gamma(xt_{1}^{m})=c_{3}$, as otherwise we are done. These imply that
either $l(e_{1})l(b^{\prime})$ or $r(e_{1})r(b^{\prime})$ provides the
required color.

$\bullet$ Suppose finally that $x$ is the endpoint of $a^{\prime}$ that is
farthest to $t^{2}_{1}$. This implies that $y$ is the endpoint of $b^{\prime}$
that is closest to $t^{2}_{1}$.

$-$ If $e_{1}=t^{1}_{1}t_{1}^{3}$, then $\gamma(\Delta(e_{1},y))=c_{1}$ and
either $l(a^{\prime})t_{1}^{1}$ or $r(a^{\prime})t_{1}^{3}$ provides the 7th
color.

$-$ If $e_{1}=t^{1}_{1}t_{1}^{2}$, then $\gamma(t_{1}^{1}y)\circeq c_{1}$ and
either $\gamma(t_{1}^{2}y)\in\\{c_{1},c_{3}\\}$ or we are done. If
$\gamma(yt_{1}^{2})=c_{1}$ (respectively, $\gamma(yt_{1}^{2})=c_{3}$) then
either $l(a^{\prime})t_{1}^{1}$ or $r(a^{\prime})t_{1}^{2}$ (respectively,
$l(a^{\prime})t_{1}^{2}$ or $r(a^{\prime})t_{1}^{3}$) provides the required
color.

$-$ If $e_{1}=t^{2}_{1}t^{3}_{1}$, then $\gamma(t_{1}^{3}y)\circeq c_{1}$ and
either $\gamma(yt^{2}_{1})\in\\{c_{1},c_{3}\\}$ or we are done. If
$\gamma(yt^{2}_{1})=c_{1}$ (respectively, $\gamma(yt^{2}_{1})=c_{3}$) then
either $l(a^{\prime})t_{1}^{2}$ or $r(a^{\prime})t_{1}^{3}$ (respectively,
$l(a^{\prime})t^{1}_{1}$ or $r(a^{\prime})t^{2}_{1}$) provides the 7th color.
∎

######  Lemma 14.

If $a\in A,b\in B$ and $Q:=T_{1}\cup\\{a,b\\}\cup T_{2}$, then $\chi(D(Q)|\geq
6$.

###### Proof.

Let $\gamma$ be an optimal coloring of $\mathcal{Q}$. By rotating $Q$ an angle
$\pi$ around the origin, if necessary, we may assume w.l.o.g that $T_{1}\cup
T_{2}$ lies on the right semiplane of the line spanned by $ab$. Similarly, we
may assume that $\gamma(ab)=c_{0}$. Since if $|\gamma(T_{1}\cup T_{2})|\geq 5$
there is nothing to prove, we can assume that $|\gamma(T_{1}\cup T_{2})|=4$ by
Corollary 9. Thus, we need to show the existence of one additional color, say
$c_{6}$.

We note that if $|\gamma(T_{1})|=1=|\gamma(T_{2})|$, then
$\gamma(T_{1}),~{}\gamma(T_{2}),~{}\gamma(t^{1}_{1}t^{1}_{2}),~{}\gamma(t^{2}_{1}t^{2}_{2})$
and $\gamma(t^{3}_{1}t^{3}_{2})$ are pairwise distinct, contradicting that
$|\gamma(T_{1}\cup T_{2})|=4$. Thus, we can assume that
$|\gamma(T_{1})|+|\gamma(T_{2})|\geq 3$.

$(1)$ Suppose that $|\gamma(T_{j})|=2$ and $|\gamma(T_{3-j})|=1$ for some
$j\in\\{1,2\\}$. Then there is a unique
$e\in\\{t^{1}_{1}t^{1}_{2},t^{2}_{1}t^{2}_{2},\\-t^{3}_{1}t^{3}_{2}\\}$ such
that $\gamma(e)\notin\gamma(T_{1})\cup\gamma(T_{2})$.

$(1.1)$ Suppose that $j=1$. Then $|\gamma(T_{1})|=2$ and $|\gamma(T_{2})|=1$.
Note that if $e=t^{1}_{1}t^{1}_{2}$, then one of $\gamma(t^{3}_{2}a)$ or
$\gamma(t^{2}_{2}b)$ must be $c_{6}$. Similarly, if $e=t^{2}_{1}t^{2}_{2}$,
then one of $\gamma(t^{1}_{2}a)$ or $\gamma(t^{3}_{2}b)$ must be $c_{6}$. Thus
we may assume that $e=t^{3}_{1}t^{3}_{2}$. Then $\gamma(t^{1}_{2}a)\circeq
c_{0}$, $\gamma(t^{3}_{2}b)\circeq\gamma(e)$, and either $l(e_{1})t^{1}_{2}$
or $r(e_{1})t^{2}_{2}$ must be colored with $c_{6}$.

$(1.2)$ Suppose that $j=2$. Then $|\gamma(T_{1})|=1$ and $|\gamma(T_{2})|=2$.
Note that if $e=t^{2}_{1}t^{2}_{2}$, then one of $\gamma(t^{1}_{1}a)$ or
$\gamma(t^{3}_{1}b)$ must be $c_{6}$. Similarly, if $e=t^{3}_{1}t^{3}_{2}$,
then one of $\gamma(t^{2}_{1}a)$ or $\gamma(t^{1}_{1}b)$ must be $c_{6}$. Thus
we may assume that $e=t^{1}_{1}t^{1}_{2}$. Then $\gamma(t^{3}_{1}b)\circeq
c_{0}$, $\gamma(t^{1}_{1}a)\circeq\gamma(e)$, and so either
$l(e_{2})t^{2}_{1}$ or $r(e_{2})t^{3}_{1}$ must be colored with $c_{6}$.

$(2)$ Suppose that $|\gamma(T_{1})|=|\gamma(T_{2})|=2$. Suppose that
$\gamma(T_{1})=\\{c_{1},c_{3}\\},\gamma(T_{2})=\\{c_{2},c_{4}\\},\gamma(e_{1})=c_{1}$
and $\gamma(e_{2})=c_{4}$. From $|\gamma(T_{1}\cup T_{2})|=4$ it follows that
there is a monochromatic triangle $\Delta$ with vertices in the endpoints of
$e_{1}$ and $e_{2}$. Then exactly one of $e_{1}\in\Delta$ or $e_{2}\in\Delta$
holds, and so $\gamma(\Delta)\in\\{c_{1},c_{4}\\}$.

$\bullet$ Suppose $e_{1}\in\Delta$. Then $\gamma(\Delta)=c_{1}$. If
$e_{1}=t^{1}_{1}t^{3}_{1}$, then either $\gamma(t^{1}_{1}a)$ or
$\gamma(t^{3}_{1}b)$ must be $c_{6}$. If $e_{1}=t^{2}_{1}t^{3}_{1}$, then
either $\gamma(t^{2}_{1}a)$ or $\gamma(t^{3}_{1}b)$ must be $c_{6}$.
Similarly, if $e_{1}=t^{1}_{1}t^{2}_{1}$, then $\gamma(t^{1}_{1}b)\circeq
c_{0}$, $\gamma(t^{1}_{1}a)\circeq c_{0},~{}\gamma(t^{2}_{1}b)\circeq c_{3}$,
and so $\gamma(t^{3}_{1}a)=c_{6}$.

$\bullet$ Suppose $e_{2}\in\Delta$. Then $\gamma(\Delta)=c_{4}$. If
$e_{2}=t^{1}_{2}t^{3}_{2}$, then either $\gamma(t^{1}_{2}a)$ or
$\gamma(t^{3}_{2}b)$ must be $c_{6}$. If $e_{2}=t^{1}_{2}t^{2}_{2}$, then
either $\gamma(t^{1}_{2}a)$ or $\gamma(t^{2}_{2}b)$ must be $c_{6}$.
Similarly, if $e_{2}=t^{2}_{2}t^{3}_{2}$ then $\gamma(t^{3}_{2}b)\circeq
c_{0}$, $\gamma(t^{3}_{2}a)\circeq c_{0},~{}\gamma(t^{2}_{2}a)\circeq c_{2}$,
and so $\gamma(t^{1}_{2}b)=c_{6}$. ∎

######  Corollary 15.

Let $\gamma$ be an optimal coloring of $D(X)$. If there are $a\in A$ and $b\in
B$ such that $|\gamma(A\cup B\setminus\\{a,b\\})|\geq 8$ and $\gamma(A\cup
B\setminus\\{a,b\\})\cap\gamma(T_{1}\cup\\{a,b\\}\cup T_{2})=\emptyset$, then
$|\gamma(X)|\geq 14$.

###### Proof.

From $\gamma(A\cup B\setminus\\{a,b\\})\cap\gamma(T_{1}\cup\\{a,b\\}\cup
T_{2})=\emptyset$ it follows that $|\gamma(X)|\geq|\gamma(A\cup
B\setminus\\{a,b\\})|+|\gamma(T_{1}\cup\\{a,b\\}\cup T_{2})|\geq 8+6$, due to
Lemma 14. ∎

######  Lemma 16.

Let $a\in A,b\in B$ and $Q:=T_{1}\cup\\{a,b\\}\cup T_{2}$. If $\gamma$ is a
coloring of $D(Q)$ such that $\gamma(ab)\neq\gamma(g)$ for any vertex
(segment) $g$ of $\mathcal{Q}\setminus\\{ab\\}$, then $|\gamma(Q)|\geq 7$.

###### Proof.

By rotating $Q$ an angle $\pi$ around the origin, if necessary, we may assume
w.l.o.g that $T_{1}\cup T_{2}$ lies on the right semiplane of the line spanned
by $ab$. Similarly, we may assume that $\gamma(ab)=c_{0}$. By Corollary 9($i$)
we know that $|\gamma(T_{1}\cup T_{2})|\geq 4$. We proceed similarly as in the
proof of Lemma 14.

(1) Suppose that $|\gamma(T_{1})|=|\gamma(T_{2})|=1$. Assume w.l.o.g. that
$\gamma(T_{1})=c_{1}$ and $\gamma(T_{2})=c_{2}$. Then
$\gamma(t^{1}_{1}t^{1}_{2})=c_{3},\gamma(t^{2}_{1}t^{2}_{2})=c_{4}$,
$\gamma(t^{3}_{1}t^{3}_{2})=c_{5}$, and so either $\gamma(t^{1}_{1}b)$ or
$\gamma(t^{1}_{2}a)$ must be the required color.

(2) Suppose that $|\gamma(T_{j})|=2$ and $|\gamma(T_{3-j})|=1$ for some
$j\in\\{1,2\\}$. From $|\gamma(T_{1}\cup T_{2})|\geq 4$ we know that there
exists $e\in\\{t^{1}_{1}t^{1}_{2},t^{2}_{1}t^{2}_{2},t^{3}_{1}t^{3}_{2}\\}$
such that $\gamma(e)\notin\gamma(T_{1})\cup\gamma(T_{2})$.

(2.1) Suppose that $j=1$. Let
$\gamma(T_{1})=\\{c_{1},c_{3}\\},\gamma(T_{2})=\\{c_{2}\\},\gamma(e_{1})=c_{1}$
and $\gamma(e)=c_{4}$. If $e=t^{1}_{1}t^{1}_{2}$, then $\gamma(t^{3}_{2}a)$
and $\gamma(t^{2}_{2}b)$ are the required colors, and if
$e=t^{2}_{1}t^{2}_{2}$ then $\gamma(t^{1}_{2}a)$ and $\gamma(t^{3}_{2}b)$ are
the required colors.

Thus we can assume that $e=t^{3}_{1}t^{3}_{2}$. Then
$\gamma(t^{1}_{2}a)=c_{5}$ and $\gamma(t^{3}_{2}b)\circeq c_{4}$. If
$e_{1}=t^{1}_{1}t^{2}_{1}$ then $\gamma(t^{1}_{1}b)\circeq c_{1}$ and so
$\gamma(t^{2}_{1}t^{2}_{2})$ is the required color. Then we can assume that
$e_{1}=t^{l}_{1}t^{3}_{1}$ for some $l\in\\{1,2\\}$. Then
$\gamma(t^{l}_{1}t^{2}_{2})\circeq c_{1}$, $\gamma(t^{3}_{1}t^{2}_{2})\circeq
c_{1}$, $\gamma(bt^{3}_{1})\circeq c_{4}$ and $\gamma(at^{3}_{2})\circeq
c_{5}$. These imply that $\gamma(t^{l}_{1}t^{1}_{2})$ is the required color.

(2.2) Suppose that $j=2$. Let
$\gamma(T_{1})=\\{c_{1}\\},\gamma(T_{2})=\\{c_{2},c_{4}\\},\gamma(e_{2})=c_{2}$,
and $\gamma(e)=c_{3}$. If $e=t^{2}_{1}t^{2}_{2}$, then $\gamma(t^{1}_{1}a)$
and $\gamma(t^{3}_{1}b)$ are the required. Similarly, if
$e=t^{3}_{1}t^{3}_{2}$ then $\gamma(t^{2}_{1}a)$ and $\gamma(t^{1}_{1}b)$ are
the required colors.

Thus we may assume that $e=t^{1}_{1}t^{1}_{2}$. Then
$\gamma(t^{3}_{1}b)=c_{5}$ and $\gamma(t^{1}_{1}a)\circeq c_{3}$. If
$e_{2}=t^{2}_{2}t^{3}_{2}$ then $\gamma(t^{2}_{1}t^{2}_{2})\circeq c_{2}$, and
so $\gamma(at^{3}_{2})$ is the required. Then $e_{2}=t^{1}_{2}t^{l}_{2}$ for
some $l\in\\{2,3\\}$ and so $\gamma(t^{2}_{1}t^{1}_{2})\circeq
c_{2},\gamma(t^{2}_{1}t^{l}_{2})\circeq c_{2}$ and $\gamma(at^{1}_{2})\circeq
c_{3}$. These imply that $\gamma(bt^{1}_{1})\circeq c_{5}$ and so
$\gamma(t^{3}_{1}t^{l}_{2})$ is the required.

(3) Suppose that $|\gamma(T_{1})|=2=|\gamma(T_{2})|$. Let
$\gamma(T_{1})=\\{c_{1},c_{3}\\},\gamma(T_{2})=\\{c_{2},c_{4}\\},\gamma(e_{1})=c_{1},$
and $\gamma(e_{2})=c_{2}$. We need to show the existence of two additional
colors, say $c_{5}$ and $c_{6}$.

(3.1) Suppose that $e_{1}=t^{1}_{1}t^{2}_{1}$. Then one of
$\gamma(bt^{1}_{1})=c_{1}$ or $\gamma(at^{2}_{1})=c_{1}$ holds, as otherwise
we are done.

$\bullet$ Suppose that $\gamma(bt_{1}^{1})=c_{1}$. Then
$\gamma(at^{2}_{1})=c_{5}$. Note that if $e_{2}=t_{2}^{l}t^{3}_{2}$ for some
$l\in\\{1,2\\}$, then $\gamma(bt_{2}^{l})\circeq c_{2}$,
$\gamma(bt^{3}_{2})\circeq c_{2}$ and $\gamma(at^{3}_{2})\circeq c_{5}$. Since
these imply $\gamma(t^{2}_{1}t^{l}_{2})=c_{6}$, we can assume
$e_{2}=t^{1}_{2}t^{2}_{2}$. Then $\gamma(bt^{1}_{2})\circeq c_{2}$,
$\gamma(bt^{2}_{2})\circeq c_{2}$, $\gamma(bt^{3}_{2})\circeq c_{4}$ and
$\gamma(t^{2}_{1}t^{1}_{2})\circeq c_{5}$, and so $\gamma(at^{2}_{2})$ must be
$c_{6}$.

$\bullet$ Suppose that $\gamma(at_{1}^{2})=c_{1}$. Then
$\gamma(bt^{1}_{1})=c_{5}$. Note that if $e_{2}=t^{1}_{2}t^{l}_{2}$ for some
$l\in\\{2,3\\}$, then $\gamma(at^{1}_{2})\circeq c_{2}$,
$\gamma(bt^{l}_{2})\circeq c_{5}$ and $\gamma(at^{1}_{1})\circeq c_{1}$. Since
these imply $\gamma(t^{2}_{1}t^{l}_{2})=c_{6}$, we can assume
$e_{2}=t^{2}_{2}t^{3}_{2}$. Then $\gamma(at^{3}_{2})\circeq c_{2}$,
$\gamma(bt^{2}_{2})\circeq c_{5}$, $\gamma(at^{1}_{1})\circeq c_{1}$, and so
$\gamma(t^{2}_{1}t^{2}_{2})=c_{6}$.

(3.2) Suppose that $e_{1}=t^{1}_{1}t^{3}_{1}$. Then either
$\gamma(at^{1}_{1})=c_{1}$ or $\gamma(bt^{3}_{1})=c_{1}$ holds, as otherwise
we are done.

$\bullet$ Suppose that $\gamma(at_{1}^{1})=c_{1}$. Then
$\gamma(bt^{3}_{1})=c_{5}$. If $t_{2}^{3}\in e_{2}$, then
$\gamma(t_{2}^{3}a)\circeq c_{2},\gamma(l(e_{2})b)\circeq c_{5}$,
$\gamma(t^{3}_{1}l(e_{2}))\circeq c_{5}$, $\gamma(at^{3}_{1})\circeq c_{1}$,
and $\gamma(bt^{1}_{1})=c_{6}$. If $t_{2}^{3}\notin e_{2}$, then
$e_{2}=t_{2}^{1}t_{2}^{2}$, and so $\gamma(t_{2}^{1}a)\circeq
c_{2},\gamma(t_{2}^{2}b)\circeq c_{5}$, $\gamma(t^{3}_{1}t_{2}^{2})\circeq
c_{5}$, $\gamma(at^{3}_{1})\circeq c_{1}$, and $\gamma(bt^{1}_{1})=c_{6}$.

$\bullet$ Suppose now that $\gamma(bt_{1}^{3})=c_{1}$. Then
$\gamma(at^{1}_{1})=c_{5}$. Note that if $e_{2}=t^{1}_{2}t^{l}_{2}$ for some
$l\in\\{2,3\\}$, then $\gamma(bt^{l}_{2})\circeq c_{2}$,
$\gamma(at^{1}_{2})\circeq c_{5}$, $\gamma(bt^{1}_{1})\circeq c_{1}$, and so
$\gamma(t^{3}_{1}t^{1}_{2})=c_{6}$. Suppose now that
$e_{2}=t^{2}_{2}t^{3}_{2}$. Then $\gamma(bt^{2}_{2})\circeq c_{2}$ and
$\gamma(bt^{3}_{2})\circeq c_{2}$, $\gamma(at^{3}_{2})\circeq c_{5}$,
$\gamma(bt^{1}_{1})\circeq c_{1}$, and hence
$\gamma(t^{3}_{1}t^{2}_{2})=c_{6}$.

(3.3) Suppose that $e_{1}=t^{2}_{1}t^{3}_{1}$. Then either
$\gamma(at^{2}_{1})=c_{1}$ or $\gamma(bt^{3}_{1})=c_{1}$ holds, as otherwise
we are done.

$\bullet$ Suppose that $\gamma(at^{2}_{1})=c_{1}$. Then
$\gamma(bt^{3}_{1})=c_{5}$. Note that if $e_{2}=t^{1}_{2}t^{l}_{2}$ for some
$l\in\\{2,3\\}$, then $\gamma(at^{1}_{2})\circeq c_{2}$,
$\gamma(bt^{l}_{2})\circeq c_{5}$, $\gamma(at^{3}_{1})\circeq c_{1}$,
$\gamma(at^{1}_{1})\circeq c_{3}$, $\gamma(bt^{2}_{1})\circeq c_{5}$ and so
$\gamma(t^{3}_{1}t^{l}_{2})=c_{6}$. Similarly, if $e_{2}=t^{2}_{2}t^{3}_{2}$
then $\gamma(at^{3}_{2})\circeq c_{2}$, $\gamma(bt^{2}_{2})\circeq c_{5}$,
$\gamma(at^{3}_{1})\circeq c_{1}$, $\gamma(at^{1}_{1})\circeq c_{3}$,
$\gamma(bt^{2}_{1})\circeq c_{5}$, and so $\gamma(t^{3}_{1}t^{2}_{2})=c_{6}$.

$\bullet$ Suppose that $\gamma(bt^{3}_{1})=c_{1}$. Then
$\gamma(at^{2}_{1})=c_{5}$. Note that if $e_{2}=t^{l}_{2}t^{3}_{2}$ for some
$l\in\\{1,2\\}$, then $\gamma(bt^{l}_{2})\circeq c_{2}$,
$\gamma(bt^{3}_{2})\circeq c_{2}$ and $\gamma(at^{3}_{2})\circeq c_{5}$. Since
these imply $\gamma(t^{2}_{1}t^{l}_{2})=c_{6}$, we can assume
$e_{2}=t^{1}_{2}t^{2}_{2}$. Then $\gamma(bt^{1}_{2})\circeq c_{2}$,
$\gamma(bt^{2}_{2})\circeq c_{2}$, $\gamma(bt^{3}_{2})\circeq c_{4}$,
$\gamma(t^{2}_{1}t^{1}_{2})\circeq c_{5}$, and so $\gamma(at^{2}_{2})=c_{6}$.
∎

######  Lemma 17.

Let $a\in A,b\in B$ and let $T_{j}$ be the triangle in $\\{T_{1},T_{2}\\}$
that is closest to $ab$. Let $Q:=T_{j}\cup\\{a,b,t\\}$ with $t\in T_{3-j}$ and
let $\gamma$ be a coloring of $D(Q)$. If $\gamma(ab)\neq\gamma(xt)$ for some
fixed $x\in\\{a,b\\}$ and $\gamma(\ell)\notin\\{\gamma(ab),\gamma(xt)\\}$ for
any $\ell\in\mathcal{Q}\setminus\\{ab,xt\\}$, then $|\gamma(Q)|\geq 6$.

###### Proof.

By rotating $Q$ an angle $\pi$ around the origin and relabeling the points of
$Q$, if necessary, we may assume w.l.o.g. that $T_{j}\cup\\{t\\}$ lies on the
right semiplane of the line spanned by $ab$. Then $T_{j}=T_{1}$ and $t\in
T_{2}$. Let $x\in\\{a,b\\}$ be as in the statement of lemma, let $y$ be such
that $\\{x,y\\}=\\{a,b\\}$, and let $\Delta:=\Delta(a,b,t)$. For brevity, let
$c_{0}=\gamma(ab)$, $c_{1}=\gamma(xt)$ and $c_{2}=\gamma(yt)$. Then
$\gamma(\Delta)=\\{c_{0},c_{1},c_{2}\\}$. Since
$|\gamma(Q)|\geq|\gamma(T_{1})|+|\gamma(\Delta)|$, we can assume
$|\gamma(T_{1})|\in\\{1,2\\}$, as otherwise we are done.

(1) Suppose that $\gamma(T_{1})=\\{c_{4}\\}$. Then we can always connect the
corners of $T_{1}$ with the corners of $\Delta$ (without creating any
intersections) by means of three pairwise disjoint segments $s_{1},s_{2}$ and
$s_{3}$. Since $\gamma(s_{1}),\gamma(s_{2}),\gamma(s_{3}),c_{0},c_{1},c_{4}$
are pairwise distinct, we are done.

(2) Suppose now that $\gamma(T_{1})=\\{c_{4},c_{5}\\}$. Let
$\gamma(e_{1})=c_{4}$. Clearly, $c_{0},c_{1},c_{2},c_{4}$ and $c_{5}$ are
pairwise distinct.

$\bullet$ Suppose that $e_{1}=t^{1}_{1}t^{3}_{1}$. Then
$\\{c_{2},c_{4}\\}=\\{\gamma(t^{1}_{1}y),\gamma(t^{3}_{1}t)\\}$ or the $6$th
color is provided by some of $t^{1}_{1}y$ or $t^{3}_{1}t$. That equality
implies that some of $t^{1}_{1}x$ or $t^{3}_{1}x$ provides the $6$th color.

$\bullet$ Suppose that $e_{1}=t^{1}_{1}t^{2}_{1}$. If $a=x$, then
$\gamma(t^{1}_{1}x)\circeq c_{4}$, $\gamma(t^{2}_{1}x)\circeq c_{4}$ and
either $\gamma(t^{1}_{1}y)$ or $\gamma(t^{2}_{1}t)$ is the $6$th color. Then
$b=x$ and so $\gamma(t^{1}_{1}x)\circeq c_{4}$, $\gamma(t_{1}^{2}t)\circeq
c_{2}$, $\gamma(t^{1}_{1}y)\circeq c_{4}$, $\gamma(t_{1}^{2}y)\circeq c_{2}$,
and either $\gamma(t^{2}_{1}x)$ or $\gamma(t_{1}^{3}t)$ is the $6$th color.

$\bullet$ Suppose that $e_{1}=t^{2}_{1}t^{3}_{1}$. If $a=x$, then
$\gamma(t^{2}_{1}x)\circeq c_{4}$, $\gamma(t^{3}_{1}x)\circeq c_{4}$,
$\gamma(t^{3}_{1}y)\circeq c_{2}$, $\gamma(t^{3}_{1}t)\circeq c_{2}$, and
either $\gamma(t^{1}_{1}x)$ or $\gamma(t^{2}_{1}y)$ is the $6$th color. Then
$b=x$ and so $\gamma(t^{3}_{1}x)\circeq c_{4}$, $\gamma(t^{2}_{1}y)\circeq
c_{2}$, $\gamma(t^{2}_{1}t)\circeq c_{2}$ and $\gamma(t^{3}_{1}t)\circeq
c_{4}$ These imply that either $\gamma(t^{2}_{1}x)$ or $\gamma(t^{1}_{1}y)$ is
the $6$th color. ∎

######  Lemma 18.

Let $a\in A,b\in B$ be such that $T_{1}$ lies on the right semiplane of the
line spanned by $ab$. Let $Q:=T_{1}\cup\\{a,b,t_{2}^{i},t_{2}^{j}\\}$ with
$1\leq i<j\leq 3$, and let $\Delta^{\prime}:=\Delta(a,t_{2}^{i},t_{2}^{j})$.
If $\gamma$ is a coloring of $D(Q)$, $|\gamma(\Delta^{\prime})|=1$,
$\gamma(ab)\neq\gamma(bt_{2}^{j})$ and
$\gamma(\ell)\notin\\{\gamma(ab),\gamma(bt_{2}^{j})\\}$ for any
$\ell\in\mathcal{Q}\setminus\\{ab,bt_{2}^{j}\\}$, then $|\gamma(Q)|\geq 7$.

###### Proof.

For brevity, let $c_{0}=\gamma(ab)$, $c_{1}=\gamma(bt_{2}^{j})$,
$c_{2}=\gamma(at_{2}^{j})$ and $\Delta=\overline{Q}$. Then
$\gamma(\Delta)=\\{c_{0},c_{1},c_{2}\\}$. Let $c_{3}=\gamma(at^{2}_{1})$,
$c_{4}=\gamma(bt^{1}_{1})$ and $c_{5}=\gamma(t^{3}_{1}t_{j}^{2})$. Clearly,
$c_{0},c_{1},\ldots,c_{5}$ are pairwise distinct. We need to show the
existence of one additional color. If $|\gamma(T_{1})|=1$, then
$\gamma(T_{1})\notin\\{c_{0},c_{1},\ldots,c_{5}\\}$ is the required color.
Then we may assume that $|\gamma(T_{1})|\geq 2$ and
$\gamma(T_{1})\subset\\{c_{3},c_{4},c_{5}\\}$, as otherwise we are done. We
also note that if $|\gamma(T_{1})|=3$, then
$\gamma(T_{1})=\\{c_{3},c_{4},c_{5}\\}$ and $bt_{2}^{i}$ provides the required
color. Then we can assume that $|\gamma(T_{1})|=2$. If
$\gamma(T_{1})=\\{c_{3},c_{4}\\}$, then $\gamma(bt_{2}^{i})\circeq c_{5}$,
$\gamma(at^{3}_{1})\circeq c_{3}$, $\gamma(t^{2}_{1}t^{3}_{1})\circeq c_{3}$,
$\gamma(t^{1}_{1}t^{2}_{1})\circeq c_{4}$ and
$\gamma(t^{1}_{1}t^{3}_{1})\circeq c_{4}$. These imply that either
$\gamma(at^{1}_{1})$ or $\gamma(bt^{2}_{1})$ is the required color. Similarly,
if $\gamma(T_{1})=\\{c_{3},c_{5}\\}$, then $\gamma(t^{1}_{1}t^{3}_{1})\circeq
c_{5}$, $\gamma(bt_{2}^{i})\circeq c_{4}$, $\gamma(t^{1}_{1}t^{2}_{1})\circeq
c_{3}$, $\gamma(at^{1}_{1})\circeq c_{3}$ and so $\gamma(t^{2}_{1}t_{2}^{i})$
is the required color. Finally, if $\gamma(T_{1})=\\{c_{4},c_{5}\\}$, then
$\gamma(bt_{2}^{i})$ is the required color. ∎

Let us introduce some notation that we will use in the rest of the paper. Let
$Q\subseteq X$ and let $e\in{\mathcal{Q}}$. If no segment of $\mathcal{Q}$
crosses $e$, we will say that $e$ is clean in $\mathcal{Q}$. Similarly, if
$p\in X$ is not incident with $e$, then $d(p,e)$ will be the euclidian
distance from $p$ to $e$.

######  Definition 1.

Let $\gamma$ be a coloring of $D(X)$ and let $\ell$ be a segment in $A*B$.
Then, (1) we shall use $U_{\ell}$ to denote the subset (may be empty) of
$T_{1}\cup T_{2}$ such that $v\in U_{\ell}$ if and only if the two segments
that join $v$ with the endpoints of $\ell$ are colored with the same color $c$
and $c\neq\gamma(\ell)$; (2) if $|U_{\ell}|<6$, we let
$v_{0},v_{1},\ldots,v_{s}$ be such that $(T_{1}\cup T_{2})\setminus
U_{\ell}=\\{v_{0},v_{1},\ldots,v_{s}\\}$ and $d(v_{i},\ell)<d(v_{j},\ell)$ for
$i<j$; (3) if $|U_{\ell}|<6$, $\Delta_{\ell}:=\Delta(\ell,v_{0})$, and
$\ell_{1}$ and $\ell_{2}$ will be the other sides of $\Delta_{\ell}$; (4) if
$|U_{\ell}|<5$, $\Delta_{i}:=\Delta(\ell_{i},v_{1})$ for $i=1,2$.

######  Proposition 19.

Let $\Delta$ be a triangle with corners in $A\cup B$, let $\ell$ be a side of
$\Delta$ such that $\ell\in A*B$, and let $Q:=T_{1}\cup\Delta\cup T_{2}$. If
$\gamma$ is an optimal coloring of $D(Q)$ and $\Delta$ contains $T_{1}\cup
T_{2}$ in its interior, then $\ell$ belongs to a star of $\gamma(Q)$ or
$|\gamma(Q)|\geq|Q|-2$.

###### Proof.

We note that $\ell$ is clean in $\mathcal{Q}$ and that $|Q|=9$. Then we must
show that $|\gamma(Q)|\geq 7$. Since $|\gamma(Q)|\geq|\gamma(T_{1}\cup
T_{2})|+|\gamma(\Delta)|\geq 4+|\gamma(\Delta)|$, then either
$|\gamma(\Delta)|\in\\{1,2\\}$ or we are done. $\bullet$ Suppose that
$|\gamma(\Delta)|=1$. Assume first that $\Delta$ has a vertex in $a\in A$ and
the other two in $b_{p},b_{q}\in B$ with $p<q$. Since $T_{1}\cup T_{2}$ lies
in the interior of $\Delta$, then $p\in\\{1,2,3\\}$ and $q\in\\{4,5\\}$. By
applying Lemma 16 to $T_{1}\cup\\{a,b_{p}\\}\cup T_{2}$ we obtain
$|\gamma(Q)|\geq 7$, as desired. The case in which $\Delta$ has an endpoint in
$b\in B$ and the other two in $A$ can be handled in a similar way.

$\bullet$ Suppose that $|\gamma(\Delta)|=2$. Then two sides, say $\ell_{1}$
and $\ell_{2}$, of $\Delta$ receive the same color and they form a star of
$\gamma|(Q)$. We can assume that $\ell\notin\\{\ell_{1},\ell_{2}\\}$, as
otherwise $\ell$ is in a star of $\gamma(Q)$, as claimed. Let $v$ be the
common endpoint of $\ell_{1}$ and $\ell_{2}$. Since $\ell_{1}$ and $\ell_{2}$
are clean in $\mathcal{Q}$, the chromatic class
$\gamma(\ell_{1})=\gamma(\ell_{2})$ is a star of $\gamma(Q)$ with apex in $v$,
and hence $|\gamma(Q\setminus\\{v\\})|=|\gamma(Q)|-1$ by Proposition 5
($iii$). Since $\ell\in A*B$, then $|\gamma(Q\setminus\\{v\\})|\geq 6$ by
Lemma 14 and so $|\gamma(Q)|\geq 7$ as required. ∎

######  Lemma 20.

Let $\Delta_{0}$ be a triangle with vertices in $A\cup B$, and let $Q\subseteq
T_{1}\cup\Delta_{0}\cup T_{2}$ with $|Q|\geq 3$. If $\gamma$ is an optimal
coloring of $D(Q)$, then $|\gamma(Q)|\geq|Q|-2$.

###### Proof.

By Proposition 5 ($i$), it is enough to verify the case in which
$Q:=T_{1}\cup\Delta_{0}\cup T_{2}$. Then, we need to show that
$|\gamma(Q)|\geq 7$. Since $|\gamma(Q)|\geq|\gamma(T_{1}\cup
T_{2})|+|\gamma(\Delta_{0})|\geq 4+|\gamma(\Delta_{0})|$, we can assume
$|\gamma(\Delta_{0})|\in\\{1,2\\}$.

Suppose first that the 3 points of $\Delta_{0}$ are in $A$. Since
$|\gamma(Q)|\leq 6$ implies $D(T_{1}\cup A\cup T_{2})\leq|\gamma(Q)|+2\leq 8$,
and this last contradicts Lemma 11, we conclude that $|\gamma(Q)|\geq 7$. An
analogous reasoning shows that $|\gamma(Q)|\geq 7$ if $\Delta_{0}\subset B$.
Then $\Delta_{0}$ has at least one vertex in each of $A$ and $B$. Let
$\ell,\ell^{\prime},\ell^{\prime\prime}$ be the sides of $\Delta_{0}$, and
assume w.l.o.g. that $\ell,\ell^{\prime}\in A*B$. Then $\ell^{\prime\prime}$
has both endpoints in either $A$ or $B$.

Case 1. Suppose that $T_{1}\cup T_{2}$ lies in the interior of $\Delta_{0}$.
By Proposition 19 we can assume that $\ell=ab$ belongs to a star with apex
$v\in\\{a,b\\}$, as otherwise we are done. If $v\in\ell^{\prime\prime}$ then
Lemma 14 implies $|\gamma(Q\setminus\\{v\\})|\geq 6$ and so $|\gamma(Q)|\geq
7$. Similarly, if $v\notin\ell^{\prime\prime}$ then Lemma 11 and Proposition 5
$(i)$ imply that $|\gamma(Q\setminus\\{v\\})|\geq 6$, and so $|\gamma(Q)|\geq
7$.

Case 2. Suppose that $T_{1}\cup T_{2}$ lies in the exterior of $\Delta_{0}$.
Assume w.l.o.g. that $\ell=ab$ (with $a\in A$ and $b\in B$) is closer to
$O=(0,0)$ than $\ell^{\prime}$. Then, $\ell^{\prime}$ and
$\ell^{\prime\prime}$ are clean in $\mathcal{Q}$.

######  Claim 1.

If $\gamma(Q)$ has a star with apex in a corner of $\Delta_{0}$, then
$|\gamma(Q)|\geq 7$.

Proof of Claim 1. Suppose that $v$ is a corner of $\Delta_{0}$ that is apex of
a star of $\gamma(Q)$. If such $v\in\ell^{\prime\prime}$, then
$|\gamma(Q\setminus\\{v\\})|\geq 6$ by Lemma 14, and so $|\gamma(Q)|\geq 7$.
Similarly, if $v\notin\ell^{\prime\prime}$ then
$|\gamma(Q\setminus\\{v\\})|\geq 6$ by Lemma 11 and Proposition 5 ($i$), and
hence $|\gamma(Q)|\geq 7$. $\triangle$

(2.1) Suppose that $|\gamma(\Delta_{0})|=1$. Then
$\ell,\ell^{\prime},\ell^{\prime\prime}$ receive the same color, and so
$\gamma$ and $T_{1}\cup\\{a,b\\}\cup T_{2}$ satisfy the hypotheses of Lemma
16. Therefore, $|\gamma(Q)|\geq 7$. (2.2) Suppose that
$|\gamma(\Delta_{0})|=2$. Then, two sides of $\Delta_{0}$ receive the same
color, say $c_{2}$. Suppose that $\gamma(\Delta_{0})=\\{c_{1},c_{2}\\}$. By
Corollary 9($i$), $|\gamma(T_{1}\cup T_{2})|\geq 4$. Since if
$|\gamma(T_{1}\cup T_{2})|=5$ there is nothing to prove, we can assume that
$\gamma(T_{1}\cup T_{2})=\\{c_{3},c_{4},c_{5},c_{6}\\}$. (2.2.1) Suppose that
$\gamma(\ell)=c_{1}$. Since $\ell^{\prime}$ and $\ell^{\prime\prime}$ are
clean in $\mathcal{Q}$ and
$\gamma(\ell^{\prime})=c_{2}=\gamma(\ell^{\prime\prime})$, then $c_{2}$ must
be a star of $\gamma(Q)$ with apex $v=\ell^{\prime}\cap\ell^{\prime\prime}$
and we are done by Claim 1. (2.2.2) Suppose that $\gamma(\ell)=c_{2}$.

######  Claim 2.

We can assume that $\gamma(\ell^{\prime})=c_{1}$ and
$\gamma(\ell)=\gamma(\ell^{\prime\prime})=c_{2}$.

Proof of Claim 2. Suppose that $\gamma(\ell)\neq\gamma(\ell^{\prime\prime})$.
From $\gamma(\ell)=c_{2}$ it follows that $\gamma(\ell^{\prime\prime})=c_{1}$,
and so $\gamma(\ell^{\prime})=c_{2}$. We recall that $\ell^{\prime\prime}$ has
its endpoints in either $A$ or $B$, and that it is clean in $\mathcal{Q}$. It
is easy to see that each segment of colored with $c_{1}$ intersects to $\ell$
and so we can recolor $\ell$ with $c_{1}$ without affecting the essential
properties of $\gamma(Q)$ (with the roles of $c_{1}$ and $c_{2}$ in
$\Delta_{0}$ interchanged). $\triangle$

######  Claim 3.

If $\gamma(Q)$ has three distinct stars with apices in $T_{1}\cup T_{2}$, then
Lemma 20 holds.

Proof of Claim 3. Let $u_{1},u_{2},u_{3}\in T_{1}\cup T_{2}$ be the apices of
such stars of $\gamma(Q)$. Then
$|\gamma(Q\setminus\\{u_{1},u_{2},u_{3}\\})|\geq 4$ by Lemma 13, and hence
$|\gamma(Q)|\geq 7$. $\triangle$

Let $\ell^{\prime}$ be as above. Let us define $U_{\ell^{\prime}}\subset
T_{1}\cup T_{2}$ as in Definition 1. From the choice of $\ell^{\prime}$ it is
not hard to see that each point of $U_{\ell^{\prime}}$ is the apex of a proper
star of $\gamma(Q)$. By Claim 3, we may asssume that $|U_{\ell^{\prime}}|\leq
2$. Let
$\\{v^{\prime}_{0},\ldots,v^{\prime}_{s}\\},\Delta_{\ell^{\prime}},\ell^{\prime}_{1},\ell^{\prime}_{2}$
and $\Delta^{\prime}_{1},\Delta^{\prime}_{2}$ be the objects corresponding to
$\ell^{\prime}$ described in Definition 1. Since $|U_{\ell^{\prime}}|\leq 2$
all these are well-defined. Let $Q^{\prime}=Q\setminus U_{\ell^{\prime}}$. By
Proposition 5 ($iii$), it is enough to show $|\gamma(Q^{\prime})|\geq
7-|U_{\ell^{\prime}}|$. We note that $\Delta_{\ell^{\prime}}$ is a separable
subset of $Q^{\prime}$ with respect to $\gamma$. Then
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta_{\ell^{\prime}})|+|\gamma(\Delta_{\ell^{\prime}})|$
by Proposition 5 ($ii$).

######  Claim 4.

$\gamma(\Delta_{\ell^{\prime}})=\\{c_{1}\\}$ or Lemma 20 holds.

Proof of Claim 4. By Claim 2 $\gamma(\ell^{\prime})=c_{1}$, and so
$c_{1}\in\gamma(\Delta_{\ell^{\prime}})$. Since
$Q^{\prime}\setminus\Delta_{\ell^{\prime}}\subset T_{1}\cup I\cup T_{2}$ for
some $I\in\\{A,B\\}$, Lemma 11 implies
$|\gamma(Q^{\prime}\setminus\Delta_{\ell^{\prime}})|\geq|Q^{\prime}\setminus\Delta_{\ell^{\prime}}|-2$,
and so
$|\gamma(Q^{\prime})|\geq|Q^{\prime}\setminus\Delta_{\ell^{\prime}}|-2+|\gamma(\Delta_{\ell^{\prime}})|$.
We note that
$|Q^{\prime}\setminus\Delta_{\ell^{\prime}}|=9-|U_{\ell^{\prime}}|-|\Delta_{\ell^{\prime}}|$.

If $|\gamma(\Delta_{\ell^{\prime}})|=|\Delta_{\ell^{\prime}}|=3$, then
$|\gamma(Q^{\prime})|\geq(9-|U_{\ell^{\prime}}|-|\Delta_{\ell^{\prime}}|)-2+|\Delta_{\ell^{\prime}}|=7-|U_{\ell^{\prime}}|$,
as required. Then we can assume that
$|\gamma(\Delta_{\ell^{\prime}})|\in\\{1,2\\}$. Since
$|\gamma(\Delta_{\ell^{\prime}})|=1$ implies
$\gamma(\Delta_{\ell^{\prime}})=\\{c_{1}\\}$, as claimed, we must have
$|\gamma(\Delta_{\ell^{\prime}})|=2$. From $v^{\prime}_{0}\notin
U_{\ell^{\prime}}$ we know that
$\gamma(\ell^{\prime}_{1})\neq\gamma(\ell^{\prime}_{2})$. Since
$|\gamma(\Delta_{\ell^{\prime}})|=2$, we must have
$c_{1}\in\\{\gamma(\ell^{\prime}_{1}),\gamma(\ell^{\prime}_{2})\\}$. In any
case, $c_{1}$ is a star with apex in $\Delta_{0}$. This last and Claim 1 imply
$|\gamma(Q)|\geq 7$. $\triangle$

######  Claim 5.

Let $f$ and $g$ be the segments that join $v^{\prime}_{s}$ with the endpoints
of $\ell^{\prime\prime}$. Then $\gamma(f)=c_{2}=\gamma(g)$ or Lemma 20 holds.

Proof of Claim 5. Let $[]$ be the convex quadrilateral formed by the 3 points
of $\Delta_{0}$ together with $v^{\prime}_{s}$. Then either $f$ or $g$ is a
side of $[]$ and the other one is a diagonal of $[]$. Suppose that $f$ (resp.
$g$) is a side (resp. diagonal) of $[]$. We start by showing that
$|\gamma([])|\in\\{2,4\\}$ implies $|\gamma(Q^{\prime})|\geq
7-|U_{\ell^{\prime}}|$, as required.

Suppose that $|\gamma([])|=2$. Then $\gamma([])=\\{c_{1},c_{2}\\}$ and
$\gamma(f)=c_{2}$. Then $\gamma(g)\neq c_{2}$ implies that $c_{2}$ is a star
of $\gamma(Q)$ with apex in a corner $v$ of $\Delta_{0}$. From this and Claim
1 we can have that $|\gamma(Q)|\geq 7$ and so $|\gamma(Q^{\prime})|\geq
7-|U_{\ell^{\prime}}|$.

If $|\gamma([])|=4$ then $[]$ is a separable subset of $Q^{\prime}$, and Lemma
11 implies $|\gamma(Q^{\prime}\setminus[])|\geq 9-|U_{\ell^{\prime}}|-|[]|-2$,
and hence
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus[])|+|\gamma([])|=(9-|U_{\ell^{\prime}}|-|[]|-2)+|[]|=7-|U_{\ell^{\prime}}|$.
Thus we can assume that $\gamma([])=\\{c_{1},c_{2},c_{3}\\}$ for some
$c_{3}\in\gamma(Q^{\prime})\setminus\\{c_{1},c_{2}\\}$. From the difinition of
$f$ it is not hard to see that $\ell^{\prime},\ell^{\prime\prime},f$ are
consecutive in $[]$ and appear in this cyclic order. Then $\ell^{\prime}\cap
f=\emptyset$ and $\gamma(\ell^{\prime})=c_{1}$ imply $\gamma(f)\neq c_{1}$.

Let $h$ be the side of $[]$ that joins $v^{\prime}_{s}$ with
$v=\ell\cap\ell^{\prime}$. From Claim 4 and $v^{\prime}_{0}\neq
v^{\prime}_{s}$ it follows that $\gamma(h)\neq c_{1}$. Similarly,
$h\cap\ell^{\prime\prime}=\emptyset$ and $\gamma(\ell^{\prime\prime})=c_{2}$
imply $\gamma(h)\neq c_{2}$. These and $\gamma([])=\\{c_{1},c_{2},c_{3}\\}$
imply $\gamma(h)=c_{3}$. From $v^{\prime}_{s}\notin U_{\ell^{\prime}}$ we have
$\gamma(f)\neq c_{3}$ and so $\gamma(f)=c_{2}$. We note that if $\gamma(g)\neq
c_{2}$, then $c_{2}$ must be a star of $\gamma(Q)$ with apex in $\Delta_{0}$,
and so we are done by Claim 1. $\triangle$

We are ready to complete the proof of $(2.2.2)$ and so the proof of Lemma 20.
Let $a^{\prime}\in A$ and $b^{\prime}\in B$ be such that
$\ell^{\prime}=a^{\prime}b^{\prime}$. We recall that
$\Delta^{\prime}_{l}=\Delta(\ell^{\prime}_{l},v^{\prime}_{1})$ for
$l\in\\{1,2\\}$. From $v^{\prime}_{1}\notin U_{\ell^{\prime}}$ we know that
$\gamma(v^{\prime}_{1}a^{\prime})\neq\gamma(v^{\prime}_{1}b^{\prime})$ and so
$|\gamma(\Delta^{\prime}_{l})|=3=|\Delta^{\prime}_{l}|$ for some
$l\in\\{1,2\\}$.

Let $f,g$ and $[]$ be as in the proof of Claim 5. Then $f$ is the side of $[]$
that joins $v^{\prime}_{s}$ with $\ell^{\prime\prime}$ and
$\gamma(f)=c_{2}=\gamma(g)$. Since $f$ is disjoint from any segment in
$\Delta^{\prime}_{l}$, then $c_{2}\notin\gamma(\Delta^{\prime}_{l})$. From
this and the fact that $\Delta^{\prime}_{l}$ is a separable subset of
$Q^{\prime}$ we know that
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta^{\prime}_{l})|+|\gamma(\Delta^{\prime}_{l})|$.

Let $v=\ell\cap\ell^{\prime}$. If $v\in\Delta^{\prime}_{l}$, then
$Q^{\prime}\setminus\Delta^{\prime}_{l}\subset T_{1}\cup I\cup T_{2}$ for some
$I\in\\{A,B\\}$, then Lemma 11 implies
$|\gamma(Q^{\prime}\setminus\Delta^{\prime}_{l})|\geq|Q^{\prime}\setminus\Delta^{\prime}_{l}|-2$.
If $v\notin\Delta^{\prime}_{l}$, then
$Q^{\prime}\setminus\Delta^{\prime}_{l}\subset T_{1}\cup\\{a,b\\}\cup T_{2}$
with $\ell=ab$, then Lemma 16 and Proposition 5 ($ii$) imply
$|\gamma(Q^{\prime}\setminus\Delta^{\prime}_{l})|\geq|Q^{\prime}\setminus\Delta^{\prime}_{l}|-2$.
In any case, we have
$|\gamma(Q^{\prime})|\geq|Q^{\prime}\setminus\Delta^{\prime}_{l}|-2+|\gamma(\Delta^{\prime}_{l})|$.
Since
$|Q^{\prime}\setminus\Delta^{\prime}_{l}|=9-|U_{\ell^{\prime}}|-|\Delta^{\prime}_{l}|$
we have
$|\gamma(Q^{\prime})|\geq(9-|U_{\ell^{\prime}}|-|\Delta^{\prime}_{l}|)-2+|\gamma(\Delta^{\prime}_{l})|=7-|U_{\ell^{\prime}}|$,
as required. ∎

######  Lemma 21.

Let $\Delta_{U}$ be a triangle with corners in $U\in\\{A,B\\}$, $y\in(A\cup
B)\setminus U$ and $Q\subseteq T_{1}\cup\Delta_{U}\cup\\{y\\}\cup T_{2}$. If
$\gamma$ is an optimal coloring of $D(Q)$, then $|\gamma(Q)|\geq|Q|-2$.

###### Proof.

By Proposition 5 ($i$), it is enough to verify the case in which
$Q=T_{1}\cup\Delta_{U}\cup\\{y\\}\cup T_{2}$. Then, we need to show that
$\gamma(Q)\geq 8$. We can assume that $\gamma$ does not have a star with apex
in a point $v\in\Delta_{U}\cup\\{y\\}$. Indeed, if such $v$ exists the
required inequality follows by applying Lemma 20 and Proposition 5 ($iii$) to
$Q\setminus\\{v\\}$. Let $u_{i},u_{j},u_{k}$ be the corners of $\Delta_{U}$
and suppose that $i<j<k$.

Let $\Delta:=\Delta(u_{i},u_{k},y)$. Then $u_{j}$ lies in the interior of
$\Delta$. Note that $\Delta_{U}$ is a separable subset of $Q$ and that its
segments are clean in $\mathcal{Q}$. Since $\gamma(\Delta_{U})=2$ implies that
$\gamma$ has a star with apex in a point of $\Delta_{U}$, we must have that
$|\gamma(\Delta_{U})|\in\\{1,3\\}$. If $|\gamma(\Delta_{U})|=3$ then
$|\gamma(Q)|\geq|\gamma(Q\setminus\Delta_{U})|+3$. Since
$|\gamma(Q\setminus\Delta_{U})|\geq 5$ by Lemma 11, we can assume
$|\gamma(\Delta_{U})|=1$.

Case 1. Suppose that $T_{1}\cup T_{2}$ lies in the interior of $\Delta$. Then
$\Delta=\overline{Q}$. Since $\gamma(u_{i}y)=\gamma(u_{k}y)$ implies that
color $\gamma(u_{i}y)$ induces a star with apex in $y$, we can assume
$\gamma(u_{i}y)\neq\gamma(u_{k}y)$. Then $|\gamma(\Delta)|=3$ and so
$|\gamma(Q)|\geq|\gamma(Q\setminus\Delta)|+3$. Since
$|\gamma(Q\setminus\Delta)|\geq 5$ by Lemma 11, we are done.

Case 2. Suppose that $T_{1}\cup T_{2}$ is in the exterior of $\Delta$. Then we
must have that $i=1,j=2$ and $k=3$. Let $\ell=u_{i}y$ and
$c_{1}=\gamma(\ell)$. We note that if a segment $f\in\\{u_{i},y\\}*(T_{1}\cup
T_{2})$ intersects $\ell$, then $f$ intersects each of $u_{j}y$ and $u_{k}y$.
Then, w.l.o.g. we can assume that $\gamma(u_{j}y)=c_{1}=\gamma(u_{k}y)$. Since
$c_{1}$ cannot be a star, there is a segment $g\in u_{i}*(T_{1}\cup T_{2})$
such that $\gamma(g)=c_{1}$. Let $\Delta^{\prime}:=\Delta(\ell,g)$. If
$\gamma(\Delta^{\prime})\neq\\{c_{1}\\}$, then $T_{1}\cup\\{u_{j},y\\}\cup
T_{2}$ satisfy the hypotheses of Lemma 16 and so
$|\gamma(Q\setminus\\{u_{i},u_{k}\\})|\geq 7$. Since $\gamma(u_{i}u_{k})$ is
not one of these 7 colors, we are done. Thus, we can assume
$\gamma(\Delta^{\prime})=\\{c_{1}\\}$.

For $\ell=u_{i}y$, let $U_{\ell}$ be as in Definition 1. From the assertions
in previous paragraph it is not hard to see that each point of $U_{\ell}$ is
the apex of a proper star of $\gamma(Q)$. By using the argumet in the proof of
Claim 3, we can asssume that $|U_{\ell}|\leq 2$. Let
$\\{v_{0},\ldots,v_{s}\\},\Delta_{\ell},\ell_{1},\ell_{2}$ and
$\Delta_{1},\Delta_{2}$ be as in Definition 1. Since $|U_{\ell}|\leq 2$, all
these are well-defined. Let $Q^{\prime}=Q\setminus U_{\ell}$. By Proposition 5
($iii$), it is enough to show that $|\gamma(Q^{\prime})|\geq 8-|U_{\ell}|$.

From the definition of $U_{\ell}$ we know that $\Delta^{\prime}\subset
Q^{\prime}$. Suppose first that $\Delta^{\prime}=\Delta_{\ell}$, and let $[]$
be the convex quadrilateral formed by the 3 points of $\Delta$ together with
$v_{s}$. Then $[]=\overline{Q^{\prime}}$. From $v_{s}\notin U_{\ell}$ and
$\gamma(\Delta_{\ell})=\\{c_{1}\\}$ it follows that $|\gamma([])|=4$. Then
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus[])|+4$. On the other
hand, Lemma 11 implies
$|\gamma(Q^{\prime}\setminus[])|\geq(10-|U_{\ell}|)-4-2=4-|U_{\ell}|$, and
hence $|\gamma(Q^{\prime})|\geq 8-|U_{\ell}|$. Suppose finally that
$\Delta^{\prime}\neq\Delta_{\ell}$. From $v_{0}\notin U_{\ell}$ it follows
that $\gamma(\ell_{1})\neq\gamma(\ell_{2})$, and so
$|\gamma(\Delta_{\ell})|=3$. Since $\Delta_{\ell}$ is a separable subset of
$Q^{\prime}$, then
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta_{\ell})|+3$. By
Lemma 11 we know that
$|\gamma(Q^{\prime}\setminus\Delta_{\ell})|\geq|Q^{\prime}\setminus\Delta_{\ell}|-2=5-|U_{\ell}|$,
as required. ∎

######  Proposition 22.

Let $[]$ be a convex quadrilateral with corners in $A\cup B$, let $\ell$ be a
side of $[]$ such that $\ell\in A*B$, and let $Q\subseteq T_{1}\cup[]\cup
T_{2}$ with $|Q|\geq 3$. If $\gamma$ is an optimal coloring of $D(Q)$ and $[]$
contains $T_{1}\cup T_{2}$ in its interior, then $\ell$ belongs to a star of
$\gamma(Q)$ or $|\gamma(Q)|\geq|Q|-2$.

###### Proof.

By Proposition 5 ($i$), it is enough to verify the case in which
$Q:=T_{1}\cup[]\cup T_{2}$. We note that $\ell$ is clean in $\mathcal{Q}$ and
that $|\gamma([])|\geq 2$. We need to show that $|\gamma(Q)|\geq 8$. Since
$|\gamma(Q)|\geq|\gamma(T_{1}\cup T_{2})|+|\gamma([])|\geq 4+|\gamma([])|$, we
can assume $|\gamma([])|\in\\{2,3\\}$.

Let $U_{\ell}$ be as in Definition 1. From the choice of $\ell$ it is not hard
to see that each point of $U_{\ell}$ is the apex of a proper star of
$\gamma(Q)$. Again, by using the argumet in the proof of Claim 3, we can
asssume that $|U_{\ell}|\leq 2$. Then, if
$\\{v_{0},\ldots,v_{s}\\},\Delta_{\ell},\ell_{1},\ell_{2}$ and
$\Delta_{1},\Delta_{2}$ are as in Definition 1, they are well-defined because
$|U_{\ell}|\leq 2$. Let $Q^{\prime}=Q\setminus U_{\ell}$. By Proposition 5
($iii$), it is enough to show $|\gamma(Q^{\prime})|\geq 8-|U_{\ell}|$.

Let $\ell^{\prime}$ be the opposite side of $\ell$ in $[]$, and note that
$c_{1}:=\gamma(\ell)\in\gamma(\Delta_{\ell})$. Since the set of points forming
$\Delta_{\ell}$ is a separable subset of $Q^{\prime}$, then
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta_{\ell})|+|\gamma(\Delta_{\ell})|$
by Proposition 5 ($ii$).

Because $Q^{\prime}\setminus\Delta_{\ell}\subset T_{1}\cup\\{a,b\\}\cup T_{2}$
for $ab=\ell^{\prime}$, then Lemma 14 and Proposition 5 ($ii$) imply
$|\gamma(Q^{\prime}\setminus\Delta_{\ell})|\geq|Q^{\prime}\setminus\Delta_{\ell}|-2$,
and so
$|\gamma(Q^{\prime})|\geq|Q^{\prime}\setminus\Delta_{\ell}|-2+|\gamma(\Delta_{\ell})|$.
We note that
$|Q^{\prime}\setminus\Delta_{\ell}|=10-|U_{\ell}|-|\Delta_{\ell}|$.

If $|\gamma(\Delta_{\ell})|=|\Delta_{\ell}|$, then
$|\gamma(Q^{\prime})|\geq(10-|U_{\ell}|-|\Delta_{\ell}|)-2+|\Delta_{\ell}|=8-|U_{\ell}|$,
as required. Then we must have $|\gamma(\Delta_{\ell})|\in\\{1,2\\}$.

$\bullet$ Suppose that $|\gamma(\Delta_{\ell})|=1$. From $v_{1}\notin
U_{\ell}$ it follows that $|\gamma(\Delta_{l})|=3$ for some $l\in\\{1,2\\}$.
Then $\Delta_{l}$ is a separable subset of $Q^{\prime}$, and hence
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta_{l})|+|\gamma(\Delta_{l})|$.
By Lemma 14 and Proposition 5 ($i$) we know that
$|\gamma(Q^{\prime}\setminus\Delta_{l})|\geq|Q^{\prime}\setminus\Delta_{l}|-2=(10-|U_{\ell}|)-2-|\Delta_{l}|$,
and hence
$|\gamma(Q^{\prime}\setminus\Delta_{l})|\geq(10-|U_{\ell}|)-2-|\Delta_{l}|+3=8-|U_{\ell}|$,
as required.

$\bullet$ Suppose that $|\gamma(\Delta_{\ell})|=2$. From $v_{1}\notin
U_{\ell}$ we know that $\gamma(\ell_{1})\neq\gamma(\ell_{2})$, and hence
$c_{1}\in\\{\gamma(\ell_{1}),\gamma(\ell_{2})\\}$. In any case, we have that
$c_{1}$ must be a star with apex in an endpoint of $\ell$, as required. ∎

######  Lemma 23.

Let $a_{i},a_{j}\in A$, $b_{p},b_{q}\in B$ and
$Q:=T_{1}\cup\\{a_{i},a_{j},b_{p},b_{q}\\}\cup T_{2}$. If $\gamma$ is an
optimal coloring of $D(Q)$, then $|\gamma(D(Q))|\geq 8$.

###### Proof.

Let $[]$ be the convex quadrilateral defined by $a_{i},a_{j},b_{p},b_{q}$.
W.l.o.g suppose that $i<j$ and $p<q$. We may assume that $\gamma$ does not
have a star with apex in a corner $v$ of $[]$. Indeed, if such $v$ exists then
we can deduce the required inequality by applying Lemma 20 and Proposition 5
($iii$) to $Q\setminus\\{v\\}$. Similarly, we can assume that $T_{1}\cup
T_{2}$ lies in the exterior of $[]$, as otherwise $|\gamma(Q)|\geq 8$ by
Proposition 22.

From $\gamma(a_{i}a_{j})\neq\gamma(b_{p}b_{q})$, we know that $\gamma([])\geq
2$. Since $\gamma(Q)\geq\gamma(T_{1}\cup T_{2})+\gamma([])$ and
$\gamma(T_{1}\cup T_{2})\geq 4$, then either $\gamma([])\in\\{2,3\\}$ or we
are done. Let $\ell_{1},\ell_{2},\ell_{3},\ell_{4}$ be the sides of $[]$ and
suppose that they appear in this cyclic (clockwise) order. W.l.o.g. let
$\ell_{1}$ (resp. $\ell_{3}$) be the farthest (resp. closest) segment of
$\\{a_{i}b_{p},a_{j}b_{q}\\}$ to $(0,0)$. For $i\in\\{1,3\\}$, let
$c_{i}=\gamma(\ell_{i})$. Clearly, $c_{1}\neq c_{3}$.

Case 1. Suppose that $\gamma([])=2$. By rotating $Q$ an angle $\pi$ around the
origin and relabeling the 10 points of $Q$, if necessary, we may assume
w.l.o.g that $T_{1}\cup T_{2}$ lies on the right semiplane of the line spanned
by $\ell_{3}$. Then, either $\gamma(\ell_{2})=c_{1},\gamma(\ell_{4})=c_{3}$ or
$\gamma(\ell_{2})=c_{3},\gamma(\ell_{4})=c_{1}$ hold.

Case 1.1. Suppose that $|\gamma(T_{2})|=1$. Let $\gamma(T_{2})=\\{c_{2}\\}$.
We first analyze the case $\gamma(\ell_{2})=c_{1}$ and
$\gamma(\ell_{4})=c_{3}$. Since $\gamma$ has no apices in $[]$, then
$\gamma(a_{j}b_{p})=c_{1}$ and so any segment colored with $c_{1}$ and
distinct from $a_{j}b_{p}$ must be incident with $a_{i}$. Moreover, we can
assume that any segment incident with $a_{i}$ is colored with color $c_{1}$.
Indeed, if necessary, we can slightly modify $\gamma$ by recoloring with
$c_{1}$ all such segments. It is not hard to see that this change does not
affect the essential properties of $\gamma(Q)$.

Clearly, $c_{2}\notin\\{c_{1},c_{3}\\}$. Let
$\Delta:=\Delta(t^{1}_{2},t^{3}_{2},a_{j})$. From $|\gamma(T_{2})|=1$ it
follows that $|\gamma(\Delta)|\in\\{2,3\\}$. Since $\Delta$ is a separable
subset of $Q$, then
$|\gamma(Q)|\geq|\gamma(Q\setminus\Delta)|+|\gamma(\Delta)|$. Since Lemma 20
implies $|\gamma(Q\setminus\Delta)|\geq|Q\setminus\Delta|-2$, we can assume
that $|\gamma(\Delta)|=2$ or we are done. Let $c_{4}$ be such that
$\gamma(\Delta)=\\{c_{2},c_{4}\\}$. Then the sides $a_{j}t^{1}_{2}$ and
$a_{j}t^{3}_{2}$ of $\Delta$ are both colored with
$c_{4}\notin\\{c_{1},c_{2},c_{3}\\}$. From $\gamma(a_{i}t^{3}_{2})=c_{1}$, and
the fact that $t^{1}_{2}t^{3}_{2}$ and $a_{i}t^{3}_{2}$ are the only segments
intersectig both $a_{j}t^{1}_{2}$ and $a_{j}t^{3}_{2}$, it follows that
$c_{4}$ must be a star with apex $a_{j}\in[]$, and we are done.

Suppose now that $\gamma(\ell_{2})=c_{3}$ and $\gamma(\ell_{4})=c_{1}$. As
$\gamma$ has no apices in $[]$, then $\gamma(a_{i}b_{q})=c_{1}$. As before, we
can assume that any segment incident with $b_{p}$ is colored with color
$c_{1}$. Let $\Delta:=\Delta(t^{2}_{2},t^{3}_{2},b_{q})$. Then, $\Delta$ is a
separable subset of $Q$ and so
$|\gamma(Q)|\geq|\gamma(Q\setminus\Delta)|+|\gamma(\Delta)|$. Since Lemma 20
implies $|\gamma(Q\setminus\Delta)|\geq|Q\setminus\Delta|-2$ and
$|\gamma(T_{2})|=1$, then $|\gamma(\Delta)|=2$ or we are done. Then
$b_{q}t^{2}_{2}$ and $b_{q}t^{3}_{2}$ are both colored with
$c_{4}\notin\\{c_{1},c_{2},c_{3}\\}$. If $|\gamma(T_{1})|=1$, then
$t_{1}^{2}t_{2}^{1}$ and $t_{1}^{3}t_{2}^{2}$ provide the $6$th and $7$th
color, and either $a_{i}t_{1}^{1}$ or $a_{j}t_{2}^{3}$ provides the $8$th
color.

Suppose now that $|\gamma(T_{1})|=2$ with $\gamma(T_{1})=\\{c_{5},c_{6}\\}$.
Clearly, $\\{c_{1},c_{2},\ldots,c_{6}\\}$ are pairwise distinct. Let $e_{1}$
be as in (N3) and suppose that $\gamma(e_{1})=c_{6}$. If
$\gamma(a_{j}t_{2}^{3})\neq c_{3}$, then $\gamma(a_{j}t_{2}^{3})$ is the $7$th
color, and either $l(e_{1})t_{2}^{1}$ or $r(e_{1})t_{2}^{2}$ provides the
$8$th color. Thus we may assume that $\gamma(a_{j}t_{2}^{3})=c_{3}$. Then some
of $l(e_{1})t_{2}^{1}$ or $r(e_{1})t_{2}^{2}$ provides the $7$th color
$c_{7}$, and the other one must be colored with $c_{6}$, as otherwise we are
done. If $\gamma(l(e_{1})t_{2}^{1})=c_{6}$ and
$\gamma(r(e_{1})t_{2}^{2})=c_{7}$, then $a_{i}t_{2}^{1}$ provides the $8$th
color. Then, we must have $\gamma(r(e_{1})t_{2}^{2})=c_{6}$ and
$\gamma(l(e_{1})t_{2}^{1})=c_{7}$, and hence $\gamma(a_{i}t_{2}^{1})\circeq
c_{7}$, $\gamma(l(e_{1})t_{2}^{2})\circeq c_{6}$ and
$\gamma(r(e_{1})t_{2}^{3})\circeq c_{4}$. If $e_{1}=t_{1}^{2}t_{1}^{3}$, then
either $a_{i}t_{1}^{1}$ or $b_{q}t_{1}^{2}$ provides the $8$th required color.
Similarly, if $e_{1}\neq t_{1}^{2}t_{1}^{3}$, then $b_{q}t_{1}^{1}$ provides
the $8$th required color.

Case 1.2. Suppose that $|\gamma(T_{1})|=1$ and $|\gamma(T_{2})|=2$. Let
$\gamma(T_{1})=\\{c_{2}\\}$ and note that $c_{2}\notin\\{c_{1},c_{3}\\}$.

(1.2.1) Suppose that $\gamma(\ell_{2})=c_{3}$ and $\gamma(\ell_{4})=c_{1}$.
Since $\gamma$ does not have a star with apex in $[]$, then
$\gamma(a_{i}b_{q})=c_{1}$ and as before, we can assume that any segment
incident with $b_{p}$ is colored with color $c_{1}$.

Let $\Delta:=\Delta(t^{1}_{1},t^{3}_{1},b_{q})$. From $|\gamma(T_{1})|=1$ it
follows that $|\gamma(\Delta)|\in\\{2,3\\}$. We note that any segment of $Q$
intersecting $\Delta$ is incident with a point of $\Delta\cup\\{b_{p}\\}$, and
so $|\gamma(Q)|\geq|\gamma(Q\setminus\Delta)|+|\gamma(\Delta)|$. Since Lemma
20 implies $|\gamma(Q\setminus\Delta)|\geq|Q\setminus\Delta|-2$, then we must
have $|\gamma(\Delta)|=2$, or we are done. Let $c_{4}$ be such that
$\gamma(\Delta)=\\{c_{2},c_{4}\\}$. Then $b_{q}t^{1}_{1}$ and $b_{q}t^{3}_{1}$
are both colored with $c_{4}\notin\\{c_{1},c_{2},c_{3}\\}$. Since any segment
that is incident with $b_{p}$ is colored with $c_{1}$, then $c_{4}$ must be a
star with apex $b_{q}$ in a corner of $[]$, and so we are done.

(1.2.2) Suppose that $\gamma(\ell_{2})=c_{1}$ and $\gamma(\ell_{4})=c_{3}$.
Since $\gamma$ does not have a star with apex in $[]$, then
$\gamma(a_{j}b_{p})=c_{1}$ and as before, we can assume that any segment
incident with $a_{i}$ is colored with color $c_{1}$.

Let $\Delta:=\Delta(t^{1}_{1},t^{2}_{1},a_{j})$. From $|\gamma(T_{1})|=1$ it
follows that $|\gamma(\Delta)|\in\\{2,3\\}$. We note that any segment of $Q$
intersecting $\Delta$ is incident with a point of $\Delta\cup\\{a_{i}\\}$, and
so $|\gamma(Q)|\geq|\gamma(Q\setminus\Delta)|+|\gamma(\Delta)|$. Since Lemma
20 implies $|\gamma(Q\setminus\Delta)|\geq|Q\setminus\Delta|-2$, then we must
have $|\gamma(\Delta)|=2$, or we are done. Let $c_{4}$ be such that
$\gamma(\Delta)=\\{c_{2},c_{4}\\}$. Then $a_{j}t^{1}_{1}$ and $a_{j}t^{2}_{1}$
are both colored with $c_{4}\notin\\{c_{1},c_{2},c_{3}\\}$.

Suppose that $\gamma(T_{2})=\\{c_{5},c_{6}\\}$, and let $e_{2}$ be as in (N3).
Suppose that $\gamma(e_{2})=c_{5}$. Clearly, some of $t_{1}^{2}l(e_{2})$ or
$t^{3}_{1}r(e_{2})$ provides a new color, say $c_{7}$, and hence
$\gamma(b_{p}t^{1}_{1})\circeq c_{3}$.

If $\gamma(t^{2}_{1}l(e_{2}))=c_{7}$, then $\gamma(t^{3}_{1}r(e_{2}))\circeq
c_{5}$ and $b_{q}t^{3}_{1}$ provides the $8$th color. Thus, we may assume that
$\gamma(t^{3}_{1}r(e_{2}))=c_{7}$, and so $\gamma(t^{2}_{1}l(e_{2}))\circeq
c_{5}$, $\gamma(b_{q}t^{3}_{1})\circeq c_{7}$, $\gamma(b_{q}r(e_{2}))\circeq
c_{7}$, $\gamma(t^{2}_{1}r(e_{2}))\circeq c_{5}$ and
$\gamma(t^{1}_{1}l(e_{2}))\circeq c_{4}$. If $t^{3}_{2}\in e_{2}$, then
$a_{j}t^{3}_{2}$ provides the $8$th color. Similarly, if $t^{3}_{2}\notin
e_{2}$ then some of $b_{q}t^{3}_{2}$ or $a_{j}t^{2}_{2}$ provides the $8$th
color. This proves Case 1.2.

Case 1.3. Suppose that $|\gamma(T_{1})|=2=|\gamma(T_{2})|$. Let
$\gamma(T_{1})=\\{c_{2},c_{4}\\}$ and $\gamma(T_{2})=\\{c_{5},c_{6}\\}$. For
$j\in\\{1,2\\}$ let $e_{j}$ be as in (N3), and let
$\gamma(e_{1})=c_{4},~{}\gamma(e_{2})=c_{6}$. Clearly,
$c_{1},c_{2},\ldots,c_{6}$ are pairwise distinct. In order to show this case,
we need the following four claims.

######  Claim 6.

If $u,v\in T_{2}$ are such that
$\gamma(Q\setminus\\{u,v\\})\subseteq\gamma(Q)\setminus\gamma(T_{2})$, then
$|\gamma(Q)|\geq 8$.

Proof of Claim 6. Suppose that $T_{2}=\\{u,v,w\\}$. Since $|\gamma(T_{2})|=2$
and $\gamma(Q\setminus\\{u,v\\})\subseteq\gamma(Q)\setminus\gamma(T_{2})$, it
is enough to show that $|\gamma(Q^{\prime})|\geq 6$ for
$Q^{\prime}=Q\setminus\\{u,v\\}$. We note that Lemma 13 guarantees
$|\gamma(Q^{\prime}\setminus\\{w\\})|\geq 5$.

Suppose first that $\gamma(\ell_{2})=c_{1}$ and $\gamma(\ell_{4})=c_{3}$.
Since $\gamma$ does not have a star with apex in $[]$, then
$\gamma(a_{j}b_{p})=c_{1}$ and as before we can assume that any segment
incident with $a_{i}$ is colored with $c_{1}$.

Let $c_{0}=\gamma(b_{q}w)$. We note that if $\gamma(a_{j}w)=c_{0}$, then
$c_{0}$ is star with apex $w$, and so
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\\{w\\})|+1=6$ by
Proposition 5 ($iii$) and Lemma 13. Thus, we may assume that
$\gamma(a_{j}w)\neq c_{0}$. Since
$c_{0}\notin\gamma(T_{1})\cup\\{c_{1},\gamma(a_{j}w)\\}$, then $c_{0}=c_{3}$
or $c_{0}$ is the $6$th required color. Since $c_{3}$ cannot be a star of
$\gamma$, then $\gamma(b_{p}w)\circeq c_{3}$. By applying Lemma 17 to
$Q^{\prime\prime}=Q^{\prime}\setminus\\{a_{i},b_{q}\\}$ we have
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime\prime})|\geq 6$, as required.

Suppose now that $\gamma(\ell_{2})=c_{3}$ and $\gamma(\ell_{4})=c_{1}$. Since
$\gamma$ does not have a star with apex in $[]$, then
$\gamma(a_{i}b_{q})=c_{1}$ and as before we can assume that any segment
incident with $b_{p}$ is colored with $c_{1}$. Let $c_{0}=\gamma(a_{j}w)$. If
$\gamma(b_{q}w)=c_{0}$, then $c_{0}$ is star with apex $w$, and so
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\\{w\\})|+1=6$ by
Proposition 5 ($iii$) and Lemma 13. Thus, we may assume that
$\gamma(b_{q}w)\neq c_{0}$. Since
$c_{0}\notin\gamma(T_{1})\cup\\{c_{1},\gamma(b_{q}w)\\}$, then $c_{0}=c_{3}$
or $c_{0}$ is the $6$th required color. Since $c_{3}$ cannot be a star of
$\gamma$, then $\gamma(a_{i}w)\circeq c_{3}$. By applying Lemma 17 to
$Q^{\prime\prime}=Q^{\prime}\setminus\\{a_{j},b_{p}\\}$ we have
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime\prime})|\geq 6$, as required.
$\triangle$

(1.3.1) Suppose that $\gamma(\ell_{2})=c_{1}$ and $\gamma(\ell_{4})=c_{3}$.
Since $\gamma$ does not have a star with apex in $[]$, then
$\gamma(a_{j}b_{p})=c_{1}$ and as before we can assume that any segment
incident with $a_{i}$ is colored with color $c_{1}$.

######  Claim 7.

$\gamma(Q)$ has a proper star with apex $u\in T_{2}$ or $|\gamma(Q)|\geq 8$.

Proof of Claim 7. Suppose that $t^{2}_{2}$ is not an apex of $\gamma(Q)$. Then
$e_{2}=t_{2}^{2}t_{2}^{k}$ for some $k\in\\{1,3\\}$. Let $l$ be such that
$\\{l,k\\}=\\{1,3\\}$ and let $\Delta:=\Delta(e_{2},a_{j})$. Additionally, we
suppose that $t_{2}^{l}$ is not an apex of $\gamma(Q)$. This implies that
$\gamma(a_{j}t^{2}_{2})=c_{5}$ and, as a consequence, any segment of
$\mathcal{Q}$ coloured with $c_{5}$ must be incident with a corner of
$\Delta$. Since $e_{2}$ and $a_{j}t^{2}_{2}$ are sides of $\Delta$,
$|\gamma(\Delta)|\geq 2$.

We now note that no color of $\gamma(\Delta)$ belongs to $\gamma(Q^{\prime})$
for $Q^{\prime}=Q\setminus\Delta$. Then
$|\gamma(Q)|\geq|\gamma(Q^{\prime})|+|\gamma(\Delta)|$. Since
$|\gamma(Q^{\prime})|\geq 5$ by Lemma 20, then $|\gamma(\Delta)|=2$ or we are
done. Then we must have that $\gamma(a_{j}t_{2}^{k})=c_{6}$. From this last it
follows that $c_{6}$ must be a star of $\gamma$ with apex $t^{k}_{2}\in
T_{2}$, as claimed. $\triangle$

By Claim 7 we know that $\gamma(Q)$ has a star with apex $u\in T_{2}$. By
Proposition 5 ($iii$), it is enough to show $|\gamma(Q^{\prime})|\geq 7$ for
$Q^{\prime}=Q\setminus\\{u\\}$. Let
$\\{t_{2}^{l},t_{2}^{k}\\}=T_{2}\setminus\\{u\\}$ with $l<k$, and let
$\Delta^{\prime}:=\Delta(t_{2}^{l},t_{2}^{k},a_{j})$. Since $\Delta^{\prime}$
is a separable subset of $Q^{\prime}$, we may assume that
$|\gamma(\Delta^{\prime})|\in\\{1,2\\}$ or we are done by Lemma 13.

Suppose that $|\gamma(\Delta^{\prime})|=1$. Then either $l(e_{1})a_{j}$ or
$r(e_{1})t_{2}^{l}$ provides the $6$th color of $\gamma(Q^{\prime})$, and so
$\gamma(b_{q}t_{2}^{k})\circeq c_{3}$. This and the fact that $b_{q}$ cannot
be apex of any star of $\gamma$ imply $\gamma(b_{p}t_{2}^{k})\circeq c_{3}$.
By applying Lemma 18 to
$Q^{\prime\prime}=Q^{\prime}\setminus\\{a_{i},b_{q}\\}$ we have
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime\prime})|\geq 7$, as required.

Suppose now that $|\gamma(\Delta^{\prime})|=2$. If
$\gamma(a_{j}t_{2}^{l})=\gamma(a_{j}t_{2}^{k})$ then $a_{j}$ is an apex of
$\gamma(Q^{\prime})$ and we are done by Lemma 20. Then $t_{2}^{l}t_{2}^{k}$
must have the same color $c^{\prime}_{5}$ that some of $a_{j}t_{2}^{l}$ or
$a_{j}t_{2}^{k}$. From this last it is easy to see that $c^{\prime}_{5}$ must
be a star of $\gamma$ with apex $v\in\\{t_{2}^{l},t_{2}^{k}\\}$, and so the
required inequality follows by applying Claim 6 to $Q\setminus\\{u,v\\}$. This
proves (1.3.1).

(1.3.2) Suppose that $\gamma(\ell_{2})=c_{3}$ and $\gamma(\ell_{4})=c_{1}$.
Since $\gamma$ does not have a star with apex in $[]$, then
$\gamma(a_{i}b_{q})=c_{1}$ and as before we can assume that any segment
incident with $b_{p}$ is colored with color $c_{1}$.

######  Claim 8.

If $u,v\in T_{1}$ are such that
$\gamma(Q\setminus\\{u,v\\})\subseteq\gamma(Q)\setminus\gamma(T_{1})$, then
$|\gamma(Q)|\geq 8$.

Proof of Claim 8. Suppose that $T_{1}=\\{u,v,w\\}$. Since $|\gamma(T_{1})|=2$
and $\gamma(Q\setminus\\{u,v\\})\subseteq\gamma(Q)\setminus\gamma(T_{1})$, it
is enough to show that $|\gamma(Q^{\prime})|\geq 6$ for
$Q^{\prime}=Q\setminus\\{u,v\\}$.

Let $c_{7}:=\gamma(b_{q}w)$ and note that
$c_{7}\notin\\{c_{1},c_{3},c_{5},c_{6}\\}$. Thus, we need to show the
existence of one additional color. Since Lemma 13 implies that
$|\gamma(Q\setminus\\{u,v,w\\})|\geq 5$, we can assume that $w$ is not an apex
of $\gamma(Q^{\prime})$. This last implies that $\gamma(a_{i}w)\neq c_{7}$,
and so $\gamma(a_{i}w)\circeq c_{3}$ and $\gamma(a_{j}w)\circeq c_{3}$. Then
we can modify $\gamma$, if necessary, by recoloring with $c_{3}$ all segments
in $a_{i}*(T_{2}\cup\\{w\\})$. It is not hard to see this modification does
not affect the essential properties of $\gamma(Q^{\prime})$.

We may assume that $c_{5}$ is a thrackle of $\gamma(Q^{\prime})$. Indeed, if
$c_{5}$ is a star with apex $x\in T_{2}$, then Proposition 5 $(iii)$ and Lemma
13 imply $|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\\{x\\})|+1\geq
6$, as required. Then $e_{2}=t_{2}^{2}t_{2}^{k}$ for some $k\in\\{1,3\\}$ and
$\gamma(a_{j}t^{2}_{2})=c_{5}$. These imply $\gamma(a_{j}t_{2}^{k})\circeq
c_{6}$ and so $c_{6}$ must be a star with apex $t_{2}^{k}$. By Proposition 5
$(iii)$ and Lemma 13 we have
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\\{t^{2}_{k}\\})|+1\geq
6$, as required. $\triangle$

######  Claim 9.

$\gamma(Q)$ has a proper star with apex $u\in T_{1}$ or $|\gamma(Q)|\geq 8$.

Proof of Claim 9. Suppose that $t_{1}^{2}$ is not an apex of $\gamma(Q)$. Then
$e_{1}=t_{1}^{2}t_{1}^{k}$ for some $k\in\\{1,3\\}$. Let $l$ be such that
$\\{l,k\\}=\\{1,3\\}$ and let $\Delta:=\Delta(e_{1},b_{q})$. Additionally, we
may assume that $t_{1}^{l}$ is not an apex of $\gamma(Q)$. This implies that
$\gamma(b_{q}t_{1}^{2})=c_{2}$ and, as a consequence, any segment of
$\mathcal{Q}$ coloured with $c_{2}$ must be incident with a corner of
$\Delta$. Since $e_{1}$ and $b_{q}t_{1}^{2}$ are sides of $\Delta$,
$|\gamma(\Delta)|\geq 2$.

We now note that no color of $\gamma(\Delta)$ belongs to $\gamma(Q^{\prime})$
for $Q^{\prime}=Q\setminus\Delta$. Then
$|\gamma(Q)|\geq|\gamma(Q^{\prime})|+|\gamma(\Delta)|$. Since
$|\gamma(Q^{\prime})|\geq 5$ by Lemma 20, then $|\gamma(\Delta)|=2$ or we are
done. Then we must have that $\gamma(b_{q}t_{1}^{k})=c_{4}$. From this last it
follows that $c_{4}$ must be a star of $\gamma$ with apex $t_{1}^{k}\in
T_{1}$, as claimed. $\triangle$

By Claim 9 we know that $\gamma(Q)$ has a star with apex $u\in T_{1}$. Let
$t_{1}^{l},t_{1}^{k}\in T_{1}\setminus\\{u\\}$ with $l<k$, and let
$\Delta^{\prime}:=\Delta(t_{1}^{l},t_{1}^{k},b_{q})$. Since $\Delta^{\prime}$
is a separable subset of $Q^{\prime}$ with respect to $\gamma$, we may assume
that $|\gamma(\Delta^{\prime})|\in\\{1,2\\}$ or we are done. Moreover, it is
not hard to see that $|\gamma(\Delta^{\prime})|=2$ implies that some chromatic
class of $\Delta^{\prime}$ is a proper star of $\gamma(Q)$ with apex
$v\in\Delta^{\prime}$. If $v=b_{q}$ the required result follows by applying
Lemma 20 and Proposition 5 ($iii$) to $Q\setminus\\{v\\}$. Similarly, if
$v\in\\{t_{1}^{l},t_{1}^{k}\\}$ we are done by Claim 8. Thus, we can assume
that $|\gamma(\Delta^{\prime})|=1$ and that neither $t_{1}^{l}$ nor
$t_{1}^{k}$ is an apex of $\gamma(Q)$. By Proposition 5 ($iii$), it is enough
to show $|\gamma(Q^{\prime})|\geq 7$ for $Q^{\prime}=Q\setminus\\{u\\}$. We
remark that $c_{1},c_{3},\gamma(\Delta^{\prime}),c_{5}$ and
$c_{6}=\gamma(e_{2})$ are pairwise distinct.

Clearly, some of $t_{1}^{k}l(e_{2})$ or $b_{q}r(e_{2})$ provides the $6$th of
$\gamma(Q^{\prime})$. If $\gamma(b_{q}r(e_{2}))$ is such $6$th color, then
$\gamma(t_{1}^{k}l(e_{2}))\circeq c_{6}$ and either $t_{1}^{l}a_{i}$ or
$t_{1}^{k}a_{j}$ provides the $7$th required color. Thus we may assume that
$\gamma(t_{1}^{k}l(e_{2}))$ is the $6$th color, say $c^{\prime}_{6}$. Then
$\gamma(b_{q}r(e_{2}))\circeq c_{6}$,
$\gamma(t_{1}^{l}l(e_{2}))=c^{\prime}_{6}$, $\gamma(t_{1}^{l}a_{i})\circeq
c_{3}$, $\gamma(t_{1}^{l}a_{j})\circeq c_{3}$, $\gamma(t_{1}^{k}a_{j})\circeq
c^{\prime}_{6}$ and $\gamma(b_{q}l(e_{2}))\circeq c_{6}$. The $7$th color is
given by $t_{2}^{3}a_{j}$ if $t_{2}^{3}\in e_{2}$, and by either
$t_{2}^{2}a_{j}$ or $b_{q}t_{2}^{3}$ when $t^{3}_{2}\notin e_{2}$. This proves
(1.3.2).

Case 2. Suppose that $\gamma([])=3$. Then one of
$\gamma(\ell_{2})\notin\\{c_{1},c_{3}\\}$ or
$\gamma(\ell_{4})\notin\\{c_{1},c_{3}\\}$ holds. Suppose that
$c_{2}=\gamma(\ell_{2})\notin\\{c_{1},c_{3}\\}$. Then
$\gamma(\ell_{4})\in\\{c_{1},c_{3}\\}$. Note that if $\gamma(\ell_{4})=c_{1}$,
then $\ell_{3}$ can be recolored with $c_{2}$ and we are done by Case 1. Then
we can assume $\gamma(\ell_{4})=c_{3}$. Since any segment that intersects
$\ell_{2}$ also intersect the diagonal $\ell^{\prime}_{2}$ of $[]$ that goes
from $\ell_{1}\cap\ell_{4}$ to $\ell_{2}\cap\ell_{3}$, we can assume that
$\gamma(\ell^{\prime}_{2})=c_{2}$. Similarly, if $\ell^{\prime}_{4}$ is the
diagonal of $[]$ that goes from $\ell_{1}\cap\ell_{2}$ to
$\ell_{3}\cap\ell_{4}$, we can assume that $\gamma(\ell^{\prime}_{4})=c_{3}$.
Since $c_{1}$ cannot be a star of $\gamma(Q)$, then $c_{1}$ must be a triangle
$\Delta$ with a side in $\ell_{1}$.

Let $U_{\ell_{1}}$ be as in Definition 1. From the definition of $\ell_{1}$ it
is not hard to see that each point of $U_{\ell_{1}}$ is the apex of a proper
star of $\gamma$. Thus, we may asssume that $|U_{\ell}|\leq 2$, as otherwise
Proposition 5 ($iii$) and Lemma 13 imply $|\gamma(Q)|\geq 8$. Let
$\\{v_{0},\ldots,v_{s}\\}$ be as in Definition 1. We remark that $s\geq 4$
because $|U_{\ell_{1}}|\leq 2$. Let $Q^{\prime}=Q\setminus U_{\ell_{1}}$. By
Proposition 5 ($iii$), it is enough to show
$|\gamma(Q^{\prime})|\geq|Q^{\prime}|-2$.

Let $v_{i}\in\\{v_{0},\ldots,v_{s}\\}$ be the corner of $\Delta$ in $T_{1}\cup
T_{2}$. Suppose first that $v_{i}=v_{0}$, let
$\Delta_{j}:=\Delta(v_{0}v_{1},x_{k})$ with $x_{k}=\ell_{1}\cap\ell_{k}$ and
$k\in\\{2,4\\}$, and let $c_{4}=\gamma(v_{0}v_{1})$. Cearly,
$c_{4}\notin\\{c_{1},c_{2},c_{3}\\}$, $x_{2}=a_{i},$ and $x_{4}=b_{p}$. It is
not hard to see that
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta_{j})|+|\gamma(\Delta_{j})|$.
Since
$|\gamma(Q^{\prime}\setminus\Delta_{j})|\geq|Q^{\prime}\setminus\Delta_{j}|-2$
by Lemma 20, we can assume that $|\gamma(\Delta_{j})|=2$ and so that
$\gamma(\Delta_{j})=\\{c_{1},c_{4}\\}$. From this last it follows that
$\gamma(v_{1}x_{2})=c_{4}=\gamma(v_{1}x_{4})$, contradicting that $v_{1}\notin
U_{\ell_{1}}$. Then we can assume that $v_{i}\neq v_{0}$. Since $v_{0}\notin
U_{\ell_{1}}$, the triangle $\Delta_{\ell_{1}}:=\Delta(\ell_{1},v_{0})$
satisfies $|\gamma(\Delta_{\ell_{1}})|=3$. Suppose that some
$c_{j}\in\\{c_{2},c_{3}\\}$ is in $\gamma(\Delta_{\ell_{1}})$. Since any
segment of color $c_{j}$ intersects to $\ell_{3}$, we can recolor $\ell_{3}$
(if necessary) with $c_{j}$. Then
$\gamma(Q^{\prime}\setminus\Delta_{\ell_{1}})=\gamma(Q^{\prime})\setminus\\{c_{1},c_{k}\\}$
with $\\{c_{j},c_{k}\\}=\\{c_{2},c_{3}\\}$ and $\ell_{3}$ is the only segment
of $Q^{\prime}\setminus\Delta_{\ell_{1}}$ colored with $c_{j}$. Moreover, we
note that in such a case $Q^{\prime}\setminus\Delta_{\ell_{1}}$ and $\ell_{3}$
satisfy the conditions of Lemma 16, and so we can conclude that
$|\gamma(Q^{\prime}\setminus\Delta_{\ell_{1}})|\geq|Q^{\prime}\setminus\Delta_{\ell_{1}}|-1$,
or equivalently, $|\gamma(Q^{\prime})|\geq|Q^{\prime}|-2$. Then we can assume
that neither $c_{2}$ nor $c_{3}$ belongs to $\gamma(\Delta_{\ell_{1}})$. From
this fact it is easy to see that
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta_{\ell_{1}})|+|\gamma(\Delta_{\ell_{1}})|$.
Since $|\gamma(\Delta_{\ell_{1}})|=3$, and
$|\gamma(Q^{\prime}\setminus\Delta_{\ell_{1}})|\geq|Q^{\prime}\setminus\Delta_{\ell_{1}}|-2$
by Lemma 14, then $|\gamma(Q^{\prime})|\geq|Q^{\prime}|-2$. The case in which
$\gamma(\ell_{4})\notin\\{c_{1},c_{3}\\}$ can be handled in a similar way. ∎

######  Lemma 24.

Let $\Delta_{U}$ be a triangle with corners in $U\in\\{A,B\\}$,
$v_{p},v_{q}\in(A\cup B)\setminus U$ and
$Q:=T_{1}\cup\Delta_{U}\cup\\{v_{p},v_{q}\\}\cup T_{2}$. If $\gamma$ is an
optimal coloring of $D(Q)$, then $|\gamma(D(Q))|\geq 9$.

###### Proof.

Let $u_{i},u_{j},u_{k}$ be the corners of $\Delta_{U}$ with $i<j<k$. W.l.o.g.
we assume that $p<q$. We may assume that $\gamma$ does not have a star with
apex $w\in\Delta_{U}$ (resp. $w\in\\{v_{p},v_{q}\\}$). Indeed, if such an apex
$w$ exists, then we can deduce the required inequality by applying Lemma 23
(resp. Lemma 21) and Proposition 5 ($iii$) to $Q\setminus\\{w\\}$. From Lemma
11 we know that $|\gamma(Q\setminus\Delta_{U})|\geq 6$. From this and the fact
that $\Delta_{U}$ is a separable triangle of $Q$, we have that
$|\gamma(Q)|\geq|\gamma(Q\setminus\Delta_{U})|+|\gamma(\Delta_{U})|\geq
6+|\gamma(\Delta_{U})|$ and so we may assume that
$|\gamma(\Delta_{U})|\in\\{1,2\\}$, as otherwise we are done. Moreover, since
$|\gamma(\Delta_{U})|=2$ implies that some vertex $w$ of $\Delta_{U}$ is an
apex of $\gamma(Q)$, we may assume $|\gamma(\Delta_{U})|=1$. Let
$c_{0}=\gamma(\Delta_{U})$ and let $[]$ be the convex quadrilateral defined by
$\\{u_{i},u_{k},v_{p},v_{q}\\}$. Since
$c_{0},\gamma(u_{i}v_{p}),\gamma(u_{k}v_{q})$ are pairwise distinct, then
$|\gamma([])|\geq 3$. See Figure 3.

Case 1. Suppose that $T_{1}\cup T_{2}$ lies in the interior of $[]$. Then
$[]=\overline{Q}$. If $\gamma([])=4$ then
$|\gamma(Q)|\geq|\gamma(Q\setminus[])|+4$. Since $|\gamma(Q\setminus[])|\geq
5$ by Lemma 11, we can assume that $|\gamma([])|=3$.

Let $c_{1}=\gamma(v_{p}v_{q})$. Let $f\in\\{u_{i}v_{p},u_{k}v_{q}\\}$ be such
that $\gamma(f)=c_{1}$. We note that $f$ exists and is uniquely determined,
because $|\gamma([])|=3$. Since $\gamma$ has no stars with an apex in $[]$,
the triangle $\Delta(f,v_{p}v_{q})$ must be colored with $c_{1}$. Let $\ell$
be the opposite segment to $f$ in $[]$, let $\ell^{\prime}:=u_{i}u_{k}$ and
let $c_{2}=\gamma(\ell)$. Then $\gamma([])=\\{c_{0},c_{1},c_{2}\\}$.

Let $U_{\ell}$ be as in Definition 1. From the choice of $\ell$ it is not hard
to see that each point of $U_{\ell}$ is the apex of a proper star of $\gamma$.
Thus, we may asssume that $|U_{\ell^{\prime}}|\leq 2$, as otherwise
Proposition 5 ($iii$) and Lemma 13 imply $|\gamma(Q)|\geq 9$. Let
$\\{v_{0},\ldots,v_{s}\\},\Delta_{\ell},\ell_{1},\ell_{2}$ and
$\Delta_{1},\Delta_{2}$ be as in Definition 1. We remark that they are well-
defined because $|U_{\ell}|\leq 2$. Let $Q^{\prime}=Q\setminus U_{\ell}$. By
Proposition 5 ($iii$), it is enough to show $|\gamma(Q^{\prime})|\geq
9-|U_{\ell}|$.

By an argument totally analogous to the one used in the proof of Claim 4, we
can assume that $\gamma(\Delta_{\ell})=\\{c_{2}\\}$. From $v_{1}\notin
U_{\ell}$ we know that $|\gamma(\Delta_{i})|=3=|\Delta_{i}|$ for some
$i\in\\{1,2\\}$. From the position of the points of $\Delta_{i}$ it is not
hard to see that any segment colored with some color in $\gamma(\Delta_{i})$
is incident with a point of $\Delta_{i}$, and hence
$|\gamma(Q^{\prime})|\geq|\gamma(Q^{\prime}\setminus\Delta_{i})|+|\gamma(\Delta_{i})|$.

If $\Delta_{i}\cap\Delta_{U}\neq\emptyset$, then
$Q^{\prime}\setminus\Delta_{i}\subset Q\setminus(\Delta_{i}\cap\Delta_{U})$
and so Lemma 23 and Proposition 5 ($ii$) imply
$|\gamma(Q^{\prime}\setminus\Delta_{i})|\geq|Q^{\prime}\setminus\Delta_{i}|-2$.
If $\Delta_{i}\cap\Delta_{U}=\emptyset$, then
$Q^{\prime}\setminus\Delta_{i}\subset
Q\setminus(\Delta_{i}\cap\\{v_{p},v_{q}\\})$ and so Lemma 21 and Proposition 5
($i$) imply
$|\gamma(Q^{\prime}\setminus\Delta_{i})|\geq|Q^{\prime}\setminus\Delta_{i}|-2$.
In any case, we have
$|\gamma(Q^{\prime})|\geq|Q^{\prime}\setminus\Delta_{i}|-2+|\gamma(\Delta_{i})|$.
Since $|Q^{\prime}\setminus\Delta_{i}|=11-|U_{\ell}|-|\Delta_{i}|$ we have
$|\gamma(Q^{\prime})|\geq(11-|U_{\ell}|-|\Delta_{i}|)-2+|\gamma(\Delta_{i})|=9-|U_{\ell}|$,
as required.

Figure 3: Here $T_{1}\cup T_{2}$ lies in the exterior of the convex
quadrilateral $[]$ formed by the thick segments. W.l.o.g. we may assume that
if $S~{}=~{}\\{u_{i},u_{j},u_{k},v_{p},v_{q}\\}$, then the segments with both
endpoints in $S$ are coloured by $\gamma$ as illustrated in some of these four
cases. In (b) $f\in v_{p}*(T_{1}\cup T_{2})$ and $g\in u_{i}*(T_{1}\cup
T_{2})$. The existence of such $f$ (resp. $g)$ it follows from the assumption
that $v_{q}$ (resp. $v_{p}$) cannot be an apex of $[]$. Similarly, we can
assume the existence of the corresponding $f$ and $g$ in (d).

Case 2. Suppose that $T_{1}\cup T_{2}$ lies in the exterior of $[]$. Then the
index $i$ of $u_{i}$ is at most 3, and hence $T_{1}\cup T_{2}$ must lie on the
right side of $[]$, as depicted in Figure 3. Let
$\ell_{1}=u_{i}v_{p},\ell_{2}=v_{p}v_{q},\ell_{3}=v_{q}u_{k}$ and
$\ell_{4}=u_{i}u_{k}$ be the sides of $[]$ and let
$S=\\{u_{i},u_{j},u_{k},v_{p},v_{q}\\}$. By Lemma13 we may assume that
$\gamma$ has at most 2 stars with apices in $T_{1}\cup T_{2}$.

######  Claim 10.

W.l.o.g. we may assume that the segments with both endpoints in $S$ are
coloured by $\gamma$ as in some of the four cases illustrated in Figure 3.

Proof of Claim 10. Suppose first that $\Delta_{U}\subset A$. Thus the points
of $S$ are accommodated as depicted in Figure 3 ($a)-(b$). Note that if
$\mathcal{S}_{1}=\\{v_{p}u_{j},v_{p}u_{k},v_{q}u_{i}\\}$, then
$\ell_{1}\cup\mathcal{S}_{1}$ form a thrackle and moreover, if
$\ell\in\mathcal{Q}\setminus\\{\ell_{1}\\}$ is such that
$\ell_{1}\cap\ell\neq\emptyset$, then $\ell\cap\ell^{\prime}\neq\emptyset$ for
each $\ell^{\prime}\in\mathcal{S}_{1}$. From these it follows that we can
recolour each segment of $\mathcal{S}_{1}$ with color $\gamma(\ell_{1})$
without affecting the essential properties of $\gamma(Q)$. We now consider two
subcases, depending on whether or not $\gamma(\ell_{1})=\gamma(\ell_{2})$.

Suppose that $\gamma(\ell_{1})=\gamma(\ell_{2})$. Then
$\gamma(u_{j}v_{q})\notin\\{\gamma(\ell_{1}),\gamma(\ell_{4})\\}$. We note
that any $\ell\in\mathcal{Q}\setminus\\{u_{j}v_{q}\\}$ with
$\gamma(\ell)=\gamma(u_{j}v_{q})$ must intersect $\ell_{3}$. Then, if
necessary, we can recolour $\ell_{3}$ with color $\gamma(u_{j}v_{q})$ without
affecting the essential properties of $\gamma(Q)$, and so we are in the case
depicted in Figure 3 ($a$).

Suppose now that $\gamma(\ell_{1})\neq\gamma(\ell_{2})$. We note that if
$\mathcal{S}_{2}=\\{v_{q}u_{i},v_{q}u_{j},v_{q}u_{k}\\}$, then
$\\{\ell_{2}\\}\cup\mathcal{S}_{2}$ is a thrackle. Moreover, note that if
$\gamma(\ell)\notin\\{\gamma(\ell_{1}),\gamma(\ell_{4})\\}$ and
$\ell\cap\ell_{2}\neq\emptyset$, then $\ell$ intersects to each segment of
$\mathcal{S}_{2}$, and so we can recolour each segment of $\mathcal{S}_{2}$
with color $\gamma(\ell_{2})$, lying in the case depicted in Figure 3 ($b$).

An analogous reasoning shows that if $\Delta_{U}\subset B$, then $\gamma(S)$
is as in some of the cases depicted in Figure 3 ($c)-(d)$. $\triangle$

From now on, we let $c_{1}=\gamma(\ell_{1})$ and $c_{3}=\gamma(\ell_{3})$. We
recall that $c_{0}=\gamma(\Delta_{U})$.

Case 2.1. Suppose that the segments in $\mathcal{S}$ are coloured by $\gamma$
as in Figure 3 ($a$). By recoloring, if necessary, we may assume that each
segment incident with $v_{p}$ is coloured with $c_{1}$. We remark that this
assumption does not affect the essential properties of $\gamma(Q)$.

Case 2.1.1. Suppose that $|\gamma(T_{1})|=1$. Let
$\Delta:=\Delta(t^{1}_{1},t^{3}_{1},v_{q})$. We note that any segment that
crosses $\Delta$ is incident with $v_{p}$ and so has color $c_{1}$. Then
$\Delta$ is a separable subset of $Q$ with respect to $\gamma$ and so we can
assume that $|\gamma(\Delta)|\in\\{1,2\\}$, as otherwise we are done by Lemma
21. This assumption and $|\gamma(T_{1})|=1$ imply that $|\gamma(\Delta)|=2$.
From this last it follows that $\gamma$ has a star with apex $v_{q}\in[]$, and
so we are done by applying Lemma 21 and Proposition 5 ($iii$) to
$Q\setminus\\{v_{q}\\}$.

Case 2.1.2. Suppose that $|\gamma(T_{1})|=2$ and $|\gamma(T_{2})|=1$. We
remark that the 5 colors in
$C=\\{c_{0},c_{1},\gamma(T_{2})\\}\cup\gamma(T_{1})$ are pairwise distinct.
Let $c_{6}=\gamma(t^{3}_{2}u_{k}),c_{7}=\gamma(t^{1}_{2}u_{j})$ and
$c_{8}=\gamma(t^{2}_{2}v_{q})$ and note that the colors in
$C\cup\\{c_{6},c_{7},c_{8}\\}$ are pairwise distinct. Then
$\gamma(l(e_{1})u_{i})\circeq\gamma(e_{1})$, $\gamma(r(e_{1})u_{j})\circeq
c_{7}$, $\gamma(t^{1}_{2}u_{k})\circeq c_{6}$ and
$\gamma(t^{3}_{2}v_{q})\circeq c_{8}$. From these it follows that
$\gamma(r(e_{1})t^{2}_{2})$ is the $9$th color.

Case 2.1.3. Suppose that $|\gamma(T_{1})|=2=|\gamma(T_{2})|$. Let $e_{2}$ be
as in (N3). $\bullet$ Suppose that $\gamma(Q)$ has 2 stars with apices $u,v\in
T_{1}$. It is enough to show that $|\gamma(Q\setminus\\{u,v\\})|\geq 7$. Let
$w$ be such that $T_{1}=\\{u,v,w\\}$. By Lemma 11 we may assume that no point
of $T_{2}\cup\\{w\\}$ is an apex of $\gamma$. We note that the 5 colors in
$C=\\{c_{0},c_{1},c_{3}\\}\cup\gamma(T_{2})$ are pairwise distinct. Then
$c_{6}=\gamma(wu_{k})$ must be the $6$th color, and so $\gamma(wv_{q})\circeq
c_{3}$. Suppose first that $t^{3}_{2}\in e_{2}$. Since $c_{3}$ cannot be a
star, then $\gamma(\Delta)=\gamma(e_{2})$ where $\Delta:=\Delta(e_{2},v_{q})$.
Then either $l(e_{2})w$ or $t_{2}^{3}u_{k}$ provides the $7$th color. Suppose
now that $t^{3}_{2}\notin e_{2}$. Then $e_{2}=t^{1}_{2}t^{2}_{2}$, and either
$\gamma(v_{q}t^{3}_{2})$ is the $7$th required color or
$\gamma(v_{q}t^{3}_{2})=\gamma(t^{1}_{2}t^{3}_{2})=\gamma(t^{2}_{2}t^{3}_{2})$.
Since these equalities imply that $t^{3}_{2}\in T_{2}$ is an apex of $\gamma$,
we are done.

$\bullet$ Suppose that $\gamma(Q)$ has exactly 1 star with apex in $T_{1}$.
Let $u$ be the only apex of $\gamma$ in $T_{1}$, and let $t_{1}^{l},t_{1}^{m}$
be such that $T_{1}=\\{u,t_{1}^{l},t_{1}^{m}\\}$ with $l<m$. By Proposition 5
($iii$), it is enough to show that $|\gamma(Q\setminus\\{u\\})|\geq 8$. Let
$\Delta:=\Delta(t_{1}^{l},t_{1}^{m},v_{q})$. We note that any segment that
crosses $\Delta$ is incident with $v_{q}$ and so has color $c_{1}$. Then
$\Delta$ is a separable subset of $Q$ with respect to $\gamma$, and so we can
assume that $|\gamma(\Delta)|\in\\{1,2\\}$, as otherwise we are done by Lemma
21. Moreover, since $|\gamma(\Delta)|=2$ implies that $\gamma$ has an apex in
a corner of $\Delta$, and this is impossible by previous assumptions, we must
have $|\gamma(\Delta)|=1$. Then $c_{7}=\gamma(t_{1}^{l}u_{k})$ is the $7$th
color, and so $\gamma(t_{1}^{m}u_{k})\circeq c_{7}$,
$\gamma(t_{1}^{m}l(e_{2}))\circeq\gamma(e_{2})$ and
$\gamma(v_{q}r(e_{2}))\circeq c_{3}$. Then $t_{1}^{l}u_{j}$ provides the $8$th
required color.

$\bullet$ Suppose that no point of $T_{1}$ is an apex of $\gamma(Q)$. Then
either $e_{1}=t^{1}_{1}t^{2}_{1}$ or $e_{1}=t^{2}_{1}t^{3}_{1}$. Let $c_{2}$
(resp. $c_{4}$) be such that $\\{c_{2},\gamma(e_{1})\\}=\gamma(T_{1})$ (resp.
$\\{c_{4},\gamma(e_{2})\\}=\gamma(T_{2})$). We remark that the 7 colors in
$C=\\{c_{0},\ldots,c_{4},\gamma(e_{1}),\gamma(e_{2})\\}$ are pairwise
distinct. Since $c_{2}$ cannot be a star of $\gamma(Q)$ and any segment
incident with $v_{p}$ is colored with $c_{1}$, then
$\gamma(v_{q}t^{2}_{1})=c_{2}$.

$-$ Suppose that $e_{1}=t^{1}_{1}t^{2}_{1}$. From
$\gamma(v_{q}t^{2}_{1})=c_{2}$ it follows that $c_{8}:=\gamma(t^{3}_{1}u_{k})$
is the $8$th color. We may assume that
$\gamma(t^{1}_{1}v_{q})\in\\{\gamma(e_{1}),c_{3}\\}$, as otherwise
$\gamma(t^{1}_{1}v_{q})$ is the required color. If
$\gamma(t^{1}_{1}v_{q})=\gamma(e_{1})$, then $\gamma(t^{2}_{1}u_{k})\circeq
c_{8}$, $\gamma(t^{2}_{1}u_{j})\circeq c_{3}$, and hence either
$l(e_{2})t^{3}_{1}$ or $r(e_{2})v_{q}$ provides the $9$th color. Suppose now
that $\gamma(t^{1}_{1}v_{q})=c_{3}$. Since $c_{3}$ cannot be a star of
$\gamma(Q)$ with apex in $v_{q}$, then neither $l(e_{2})v_{q}$ nor
$r(e_{2})v_{q}$ is colored $c_{3}$. Then
$\gamma(v_{q}l(e_{2}))\circeq\gamma(e_{2})\circeq\gamma(v_{q}r(e_{2}))$. If
$t^{3}_{2}\in e_{2}$, then either $t^{3}_{1}l(e_{2})$ or $t^{3}_{2}u_{k}$
provides the $9$th color, and if $t^{3}_{2}\notin e_{2}$ then
$\gamma(t^{3}_{1}t^{1}_{2})\circeq c_{8}$, $\gamma(t^{3}_{2}v_{q})\circeq
c_{4}$ and so the $9$th required color is provided by $t^{2}_{2}u_{k}$.

$-$ Suppose that $e_{1}=t^{2}_{1}t^{3}_{1}$. From
$\gamma(v_{q}t^{2}_{1})=c_{2}$ it follows that $c_{8}:=\gamma(t^{1}_{1}u_{k})$
is the $8$th color. We may assume that
$\gamma(t^{3}_{1}v_{q})\in\\{\gamma(e_{1}),c_{3}\\}$, as otherwise
$\gamma(t^{3}_{1}v_{q})$ is the required color. If
$\gamma(t^{3}_{1}v_{q})=\gamma(e_{1})$, then
$\gamma(t^{2}_{1}l(e_{2}))\circeq\gamma(e_{2})$, $\gamma(r(e_{2})v_{q})\circeq
c_{3}$, $\gamma(t^{1}_{1}u_{j})\circeq c_{8}$ and so $t^{2}_{1}u_{k}$ provides
the $9$th color. Suppose now that $\gamma(t^{3}_{1}v_{q})=c_{3}$. Then
$\gamma(t^{1}_{1}u_{j})\circeq c_{8}$. Since $c_{3}$ cannot be a star of
$\gamma(Q)$, then $\gamma(v_{q}r(e_{2}))\circeq\gamma(e_{2})$,
$\gamma(t^{3}_{1}l(e_{2}))\circeq\gamma(e_{1})$ and $t^{2}_{1}u_{k}$ provides
the $9$th color.

Case 2.2. Suppose that the segments in $\mathcal{S}$ are coloured by $\gamma$
as in Figure 3 ($b$).

Case 2.2.1. Suppose that $|\gamma(T_{1})|=1=|\gamma(T_{2})|$. Let
$c_{6}:=\gamma(t^{1}_{1}t^{1}_{2})$, $c_{7}:=\gamma(t^{2}_{1}t^{2}_{2})$ and
$c_{8}:=\gamma(t^{3}_{1}t^{3}_{2})$. Clearly, the 8 colors
$c_{0},c_{1},c_{3},c_{6},c_{7},c_{8},\gamma(T_{1}),\gamma(T_{2})$ are pairwise
distinct. Then either $t^{1}_{1}u_{j}$ or $t^{1}_{2}u_{k}$ provides the $9$th
color.

Case 2.2.2. Suppose that $|\gamma(T_{1})|=1$ and $|\gamma(T_{2})|=2$. Let
$\gamma(T_{1})=\\{c_{2}\\}$, $\gamma(T_{2})=\\{c_{4},\gamma(e_{2})\\}$,
$c_{7}:=\gamma(t^{3}_{1}u_{k})$ and $c_{8}:=\gamma(t^{2}_{1}u_{j})$. Then the
$8$ colors $c_{0},c_{1},c_{2},c_{3},c_{4},c_{7},c_{8},\gamma(e_{2})$ are
pairwise distinct. Then $\gamma(t^{1}_{1}u_{j})\circeq c_{8}$,
$\gamma(t^{2}_{1}u_{k})\circeq c_{7}$,
$\gamma(t_{1}^{3}l(e_{2}))\circeq\gamma(e_{2})$,
$\gamma(t_{1}^{3}r(e_{2}))\circeq\gamma(e_{2})$ and
$\gamma(t^{3}_{1}v_{p})\circeq c_{3}$. Then $r(e_{2})v_{q}$ provides the $9$th
color.

Case 2.2.3. Suppose that $|\gamma(T_{1})|=2$ and $|\gamma(T_{2})|=1$. Let
$\gamma(T_{1})=\\{c_{2},\gamma(e_{1})\\}$, $\gamma(T_{2})=\\{c_{4}\\}$,
$c_{7}:=\gamma(t^{3}_{2}u_{k})$ and $c_{8}:=\gamma(t^{1}_{2}u_{j})$. Then the
$8$ colors $c_{0},c_{1},c_{2},c_{3},c_{4},c_{7},c_{8},\gamma(e_{1})$ are
pairwise distinct. Then $\gamma(l(e_{1})t_{2}^{2})\circeq\gamma(e_{1})$,
$\gamma(r(e_{1})t_{2}^{2})\circeq\gamma(e_{1})$, $\gamma(l(e_{1})u_{j})\circeq
c_{8}$ and $\gamma(t^{1}_{2}u_{k})\circeq c_{7}$. Then $t^{3}_{2}r(e_{1})$
provides the $9$th color.

Case 2.2.4. Suppose that $|\gamma(T_{1})|=2=|\gamma(T_{2})|$. Let
$\gamma(T_{1})=\\{c_{2},\gamma(e_{1})\\}$ and
$\gamma(T_{2})=\\{c_{4},\gamma(e_{2})\\}$.

$\bullet$ Suppose that $\gamma(Q)$ has 2 stars with apices $u,v\in T_{1}$. It
is enough to show that $|\gamma(Q\setminus\\{u,v\\})|\geq 7$. Let $w$ be such
that $T_{1}=\\{u,v,w\\}$. By Lemma 11 we may assume that no point of
$T_{2}\cup\\{w\\}$ is an apex of $\gamma(Q)$. We note that the 5 colors
$c_{0},c_{1},c_{3},c_{4},\gamma(e_{2})$ are pairwise distinct.

Then $c_{6}:=\gamma(wu_{j})$ must be the $6$th color, and so
$\gamma(wu_{k})\circeq c_{6}$. Since $t_{2}^{2}$ cannot be an apex of
$\gamma$, then either $e_{2}=t_{2}^{1}t_{2}^{2}$ or
$e_{2}=t_{2}^{2}t_{2}^{3}$. If $e_{2}=t_{2}^{1}t^{2}_{2}$, then
$\gamma(t^{1}_{2}u_{k})\circeq\gamma(e_{2})$, $\gamma(t^{3}_{2}u_{k})\circeq
c_{4}$, $\gamma(wt^{2}_{2})\circeq c_{6}$, and so
$\gamma(wt^{1}_{2})\in\\{\gamma(e_{2}),c_{6}\\}$. We note that if
$\gamma(wt^{1}_{2})=\gamma(e_{2})$ (respectively, $\gamma(wt^{1}_{2})=c_{6})$)
then $t^{1}_{2}$ (respectively, $w$) is an apex of $\gamma$, contradicting
that $\gamma(T_{2}\cup\\{w\\})$ has no apices. Thus $e_{2}=t_{2}^{2}t_{2}^{3}$
and so $\gamma(t^{3}_{2}u_{k})\circeq\gamma(e_{2})$. Since $\gamma(e_{2})$
cannot be a star, then $\gamma(t_{2}^{2}u_{k})\circeq\gamma(e_{2})$,
$\gamma(t_{2}^{3}w)\circeq c_{6}$ and $\gamma(t_{2}^{2}w)\circeq c_{6}$. But
these imply that $c_{6}$ is a star with apex in $w$, a contradiction.

$\bullet$ Suppose that $\gamma(Q)$ has exactly 1 star with apex in $T_{1}$.
Let $u$ be the only apex of $\gamma$ in $T_{1}$, let $t_{1}^{l},t_{1}^{m}$ be
such that $T_{1}=\\{u,t_{1}^{l},t_{1}^{m}\\}$ with $l<m$, and let
$e=t_{1}^{l}t_{1}^{m}$. It is enough to show that
$|\gamma(Q\setminus\\{u\\})|\geq 8$.

We note that the 6 colors $c_{0},c_{1},c_{3},c_{4},\gamma(e),\gamma(e_{2})$
are pairwise distinct. Clearly, either $t_{1}^{l}u_{j}$ or $t_{1}^{m}u_{k}$
provides the $7$th color $c_{7}$.

$-$ Suppose that $\gamma(t_{1}^{l}u_{j})=c_{7}$. Then
$\gamma(t_{1}^{m}u_{k})\circeq\gamma(e)$. Since $t_{1}^{m}$ cannot be an apex,
there is $h\in t_{1}^{l}*T_{2}$ such that $\gamma(h)=\gamma(e)$.

If $t_{2}^{3}\in e_{2}$, then $\gamma(t_{2}^{3}u_{k})\circeq\gamma(e_{2})$,
$\gamma(l(e_{2})t_{1}^{m})\circeq\gamma(e)$ and $\gamma(l(e_{2})v_{q})\circeq
c_{3}$. These and the existence of $h$ imply $\gamma(t_{1}^{m}v_{p})\circeq
c_{1}$ and $\gamma(t_{1}^{m}u_{i})\circeq c_{1}$. Since $t_{1}^{l}$ cannot be
an apex, then $t_{1}^{l}v_{p}$ cannot be colored $c_{7}$, and so
$t_{1}^{l}v_{p}$ provides the required $8$th color. Similarly, if
$t_{2}^{3}\notin e_{2}$ then $e_{2}=t_{2}^{1}t_{2}^{2}$, and so
$\gamma(t_{2}^{1}u_{k})\circeq\gamma(e_{2})$,
$\gamma(t_{2}^{2}t_{1}^{m})\circeq\gamma(e)$ and