[{"OA_place":"publisher","author":[{"last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek","first_name":"Marek"},{"last_name":"Nakajima","full_name":"Nakajima, Tamio Vesa","first_name":"Tamio Vesa"},{"first_name":"Jakub","full_name":"Opršal, Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","last_name":"Opršal","orcid":"0000-0003-1245-3456"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","last_name":"Tasinato","first_name":"Gianluca","full_name":"Tasinato, Gianluca"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"quality_controlled":"1","citation":{"mla":"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>.","ista":"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.","ama":"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>","chicago":"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>.","apa":"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>","ieee":"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.","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, ACM Transactions on Computation Theory 18 (2026)."},"publisher":"Association for Computing Machinery","status":"public","date_published":"2026-05-04T00:00:00Z","external_id":{"arxiv":["2312.12981"]},"publication_identifier":{"eissn":["1942-3462"],"issn":["1942-3454"]},"PlanS_conform":"1","article_type":"original","file_date_updated":"2026-07-06T09:03:02Z","doi":"10.1145/3779121","department":[{"_id":"UlWa"}],"keyword":["Constraint satisfaction problem","hypergraph colouring","promise problem","topological methods"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1145/3779121","volume":18,"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"project":[{"call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"},{"grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"publication_status":"published","oa":1,"ddc":["500"],"ec_funded":1,"day":"04","date_created":"2026-07-05T22:01:37Z","scopus_import":"1","language":[{"iso":"eng"}],"corr_author":"1","oa_version":"Published Version","_id":"22247","file":[{"file_id":"22252","access_level":"open_access","date_updated":"2026-07-06T09:03:02Z","file_name":"2026_TransactionsGraphics_Filakovsky.pdf","creator":"dernst","relation":"main_file","success":1,"file_size":941518,"date_created":"2026-07-06T09:03:02Z","checksum":"0399ab94085878fc810084845eabd627","content_type":"application/pdf"}],"month":"05","arxiv":1,"date_updated":"2026-10-21T13:23:55Z","researchdata_availability":"no","publication":"ACM Transactions on Computation Theory","year":"2026","license":"https://creativecommons.org/licenses/by/4.0/","abstract":[{"lang":"eng","text":"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).\r\nHere, 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)."}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"15168"}]},"has_accepted_license":"1","intvolume":"        18","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","type":"journal_article","OA_type":"gold","article_processing_charge":"Yes","issue":"2","acknowledgement":"This research was supported by the Charles University project PRIMUS/21/SCI/014, by the Ministry of Education, Youth\r\nand Sports of the Czech Republic under the project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229), and by the\r\nAustrian Science Fund (FWF project P31312-N35). This research was funded by UKRI EP/X024431/1 and by a Clarendon\r\nFund Scholarship. This project has received funding from the European Union’s Horizon 2020 research and innovation\r\nprogramme under the Marie Skłodowska-Curie Grant Agreement No 101034413.\r\n","das_tickbox":"0","supplementarymaterial":"no","article_number":"10"}]