2026-07-26T05:31:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19744 2024-03-11T06:37:04Z ddc:004 open_access

Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs Filakovský, Marek Nakajima, Tamio-Vesa Opršal, Jakub Tasinato, Gianluca Wagner, Uli constraint satisfaction problem hypergraph colouring promise problem topological methods A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marek Filakovský and Tamio-Vesa Nakajima and Jakub Opršal and Gianluca Tasinato and Uli Wagner 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.34 urn:nbn:de:0030-drops-197445 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.34 eng https://creativecommons.org/licenses/by/4.0/legalcode