  A linearly ordered (LO) $k$-colouring of an $r$-uniform hypergraph assigns an
integer from $\{1, \ldots, k \}$ to every vertex so that, in every edge, the
(multi)set of colours has a unique maximum. Equivalently, for $r=3$, if two
vertices in an edge are assigned the same colour, then the third vertex is
assigned a larger colour (as opposed to a different colour, as in classic
non-monochromatic colouring). Barto, Battistelli, and Berg [STACS'21] studied
LO colourings on $3$-uniform hypergraphs in the context of promise constraint
satisfaction problems (PCSPs). We show two results.
  First, given a 3-uniform hypergraph that admits an LO $2$-colouring, one can
find in polynomial time an LO $k$-colouring with $k=O(\sqrt[3]{n \log \log n /
\log n})$.
  Second, given an $r$-uniform hypergraph that admits an LO $2$-colouring, we
establish NP-hardness of finding an LO $k$-colouring for every constant
uniformity $r\geq k+2$. In fact, we determine relationships between
polymorphism minions for all uniformities $r\geq 3$, which reveals a key
difference between $r<k+2$ and $r\geq k+2$ and which may be of independent
interest. Using the algebraic approach to PCSPs, we actually show a more
general result establishing NP-hardness of finding an LO $k$-colouring for LO
$\ell$-colourable $r$-uniform hypergraphs for $2 \leq \ell \leq k$ and $r \geq
k - \ell + 4$.
