2026-07-23T08:35:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23546 2025-10-02T12:58:24Z ddc:004 open_access

Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings Nakajima, Tamio-Vesa Verwimp, Zephyr Wrochna, Marcin Živný, Stanislav hypergraph colourings conflict-free colourings unique-maximum colourings linearly-ordered 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 et al. [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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tamio-Vesa Nakajima and Zephyr Verwimp and Marcin Wrochna and Stanislav Živný 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.169 urn:nbn:de:0030-drops-235460 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.169 eng https://creativecommons.org/licenses/by/4.0/legalcode