= Solution
For each <vertex> $v$, let $c(v)$ be the <maximum> number of <vertices> in a <directed path> ending at $v$. These numbers lie between one and $\ell$.
If $u\to v$ is an <edge>, a longest <graph path> ending at $u$ cannot already contain $v$, since that would give a <directed cycle> on appending $u\to v$. Appending it therefore creates a <graph path> ending at $v$, so $c(v)\geq c(u)+1$. Adjacent <vertices> consequently receive different colours. Hence
$$
\boxed{c\text{ is a proper colouring using at most }\ell\text{ colours}.}
$$
Acyclicity is exactly what justifies extending the <graph path> without repeating a <vertex>.
Back to article page
