x $\ell_0$ to a perfect graph, and is, therefore, also perfect. $\Box$

[**Proof of Theorem 2.**]{} We start with the proof of part (ii). Let $G$ be a disjointness graph of lines in ${{\mathbb P}}^d$. Let $C\subseteq G$ be a maximal clique in $G$. Clearly, $|C|\le\omega(G)$. By the maximality of $C$, for every $\ell\in V(G)\setminus C$, there exists $c\in C$ that is not adjacent to $\ell$ in $G$. Hence, there is a partition of $V(G)$ into disjoint sets $V_c, c\in C,$ such that $c\in V_c$ and $c$ is an isolated vertex in the induced subgraph $G[V_c]$ of $G$. Applying Claim 2.1 separately to each subgraph $G[V_c]$, we obtain $$\chi(G)\le\sum_{c\in C}\chi(G[V_c])=\sum_{c\in C}\omega(G[V_c])
\le|C|\omega(G)\le(\omega(G))^2.$$

Now we turn to the proof of part (i) of Theorem 2. Let $G$ be a disjointness graph of lines in ${{\mathbb R}}^d$. Consider the lines in $V(G)$ as lines in the projective space ${{\mathbb P}}^d$, and consider the disjointness graph $G'$ of these projective lines. Clearly, $G'$ is a subgraph of $G$ with the lines $\ell$, $\ell'\in V(G)$ adjacent in $G$ but not adjacent in $G'$ if and only if $\ell$ and $\ell'$ are parallel. Thus, an independent set in $G'$ induces a disjoint union of complete subgraphs in $G$, where the vertices of each complete subgraph correspond to pairwise parallel lines. If $k$ is the maximal number of pairwise parallel lines in $V(G)$, then $k\le\omega(G)$ and each independent set in $G'$ can be partitioned into at most $k$ independent sets in $G$. Applying part (ii), we obtain $$\chi(G)\le k\chi(G')\le \omega(G)(\omega(G'))^2\le(\omega(G))^3.$$

Finally, we prove the last claim concerning polynomial time algorithms. In the proof of part (ii), we first took a maximal clique $C$ in $G$. Such a clique can be efficiently found by a greedy algorithm. The partition of $V(G)$ into subsets $V_c, c\in C,$ such that $c\in V_c$ is an isolated vertex in the subgraph $G[V_c]$, can also be done efficiently. It remains to find a clique of maximum size and a proper coloring of each perfec