A logarithmic approximation of linearly-ordered colourings

A linearly ordered (LO) k-colouring of a hypergraph assigns to each vertex a colour from the set \0,1,…,k-1\ in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO k-colouring of an LO 2-colourable 3-uniform hypergraph for any constant k≥ 2 [STACS'21] but even the case $k=3$ is still open. Nakajima and {Z}ivn\'{y} gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with O^*(√n) colours [ICALP'22] and an LO colouring with O^*(√[3]n) colours [ACM ToCT'23]. We present a simple polynomial-time algorithm that finds an LO colouring with log₂(n) colours, which is an exponential improvement.