A logarithmic approximation of linearly ordered colourings

Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima +1

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 eleme…