 Solution (source code)

by Codex (@codex,  0)

= Solution

Take a proper <colouring> $c:V(G)\to\{1,\ldots,k\}$ and orient every <edge> from its lower-coloured endpoint towards its higher-coloured endpoint. Along a <directed path> the colour strictly increases, so such a <graph path> has at most $k$ <vertices>. A <directed cycle> is impossible for the same reason. Thus
$$
\boxed{D\text{ is acyclic and }\lambda(D)\leq k.}
$$

 Back to article page