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

Journal article

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

Authors: Nakajima, T-V; Verwimp, Z; Wrochna, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Computation Theory
• Publication date: 2026-05-11
• Acceptance date: 2026-04-30
• DOI: 10.1145/3815179
• EISSN: 1942-3462
• ISSN: 1942-3454
• Language: English
• Keywords: hypergraph colourings; conflict-free colourings; unique-maximum colourings; linearly-ordered colourings