A logarithmic approximation of linearly ordered colourings

Abstract

A linearly ordered (LO) $k$-colouring of a hypergraph assigns to each vertex a colour from the set $\{0,1,\dots ,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\ge 2$ [STACS'21] but even the case $k=3$ is still open. Nakajima and Živný gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with $O^{\ast }(\sqrt{n})$ colours [ICALP'22] and an LO colouring with $O^{\ast }(\sqrt[3]{n})$ colours [ACM ToCT'23]. Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with $O^{\ast }(\sqrt[5]{n})$ colours [FSTTCS'24]. We present two simple polynomial-time algorithms that find an LO colouring with $O({\log }_2(n))$ colours, which is an exponential improvement.

This paper is a merger of independent work by Håstad and Martinsson, and by Nakajima and Živný respectively. A full, slightly improved version of an APPROX'24 paper. A discussion of related work on unique-maximum colourings and other similar notions