Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings

Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an ℓ-colouring of a k -colourable r -uniform hypergraph is NP-hard for all constant 2 ≤ k ≤ ℓ and r ≥ 3. This provides a shorter proof of a celebrated result by Dinur, Regev, and Smyth [FOCS’02/Combinatorica’05]. Secondly, we show that finding an ℓ-conflict-free colouring of an r -uniform hypergraph that admits a k -conflict-free colouring is NP-hard for all constant 2 ≤ k ≤ ℓ and r ≥ 4, except for r = 4 and k = 2 (and any ℓ); this case is solvable in polynomial time. The case of r = 3 is the standard nonmonochromatic colouring, and the case of r = 2 is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an ℓ-linearly-ordered colouring of an r -uniform hypergraph that admits a k -linearly-ordered colouring is NP-hard for all constant 3 ≤ k ≤ ℓ and r ≥ 4, thus improving on the results of Nakajima and Živný [ICALP’22/ACM ToCT’23].