article published yes Marek Filakovský author 3E8AF77E-F248-11E8-B48F-1D18A9856A87 Tamio Vesa Nakajima author Jakub Opršal author ec596741-c539-11ec-b829-c79322a912420000-0003-1245-3456 Gianluca Tasinato author 0433290C-AF8F-11E9-A4C7-F729E6697425 Uli Wagner author 36690CA2-F248-11E8-B48F-1D18A9856A870000-0002-1494-0568 UlWa department Algorithms for Embeddings and Homotopy Theory project IST-BRIDGE: International postdoctoral program project 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). https://research-explorer.ista.ac.at/download/22247/22252/2026_TransactionsGraphics_Filakovsky.pdf application/pdfno Association for Computing Machinery2026 eng Constraint satisfaction problemhypergraph colouringpromise problemtopological methods 1942-3454 1942-3462 2312.1298110.1145/3779121 182 https://research-explorer.ista.ac.at/record/15168 Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>ACM Transactions on Computation Theory</i>. Association for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3779121">https://doi.org/10.1145/3779121</a>. 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> Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>ACM Transactions on Computation Theory</i>, vol. 18, no. 2, 10, Association for Computing Machinery, 2026, doi:<a href="https://doi.org/10.1145/3779121">10.1145/3779121</a>. Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2026). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. <i>ACM Transactions on Computation Theory</i>. Association for Computing Machinery. <a href="https://doi.org/10.1145/3779121">https://doi.org/10.1145/3779121</a> M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” <i>ACM Transactions on Computation Theory</i>, vol. 18, no. 2. Association for Computing Machinery, 2026. M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, ACM Transactions on Computation Theory 18 (2026). Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2026. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. ACM Transactions on Computation Theory. 18(2), 10. 222472026-07-05T22:01:37Z2026-07-06T09:06:29Z