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

Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna +1

Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmo…