Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs

Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal +2

A linearly ordered (LO) $k$-colouring of a hypergraph is a colouring of its vertices with colours $1,\dots ,k$ such that each edge contains a unique maximal colour. Deciding wheth…