Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs Filakovský, Marek Nakajima, Tamio Vesa Opršal, Jakub ; https://orcid.org/0000-0003-1245-3456 Tasinato, Gianluca Wagner, Uli ; https://orcid.org/0000-0002-1494-0568 Constraint satisfaction problem hypergraph colouring promise problem topological methods ddc:500 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). Association for Computing Machinery 2026 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/22247 https://research-explorer.ista.ac.at/download/22247/22252 Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. <i>ACM Transactions on Computation Theory</i>. 2026;18(2). doi:<a href="https://doi.org/10.1145/3779121">10.1145/3779121</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/3779121 info:eu-repo/semantics/altIdentifier/issn/1942-3454 info:eu-repo/semantics/altIdentifier/e-issn/1942-3462 info:eu-repo/semantics/altIdentifier/arxiv/2312.12981 info:eu-repo/semantics/openAccess