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].