[{"conference":{"name":"STOC: Symposium on Theory of Computing","end_date":"2025-06-27","start_date":"2025-06-23","location":"Prague, Czechia"},"type":"conference","acknowledgement":"This research was supported by the Austrian Science Fund (FWF project P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed by the Ministry of Education, Youth and Sports of the Czech Republic. This project has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.","OA_place":"publisher","file":[{"checksum":"2c9ae7ad0102c41124976f4cb5182760","content_type":"application/pdf","relation":"main_file","file_size":940827,"file_id":"20013","creator":"dernst","access_level":"open_access","success":1,"date_updated":"2025-07-14T06:42:58Z","date_created":"2025-07-14T06:42:58Z","file_name":"2025_STOC_Avvakumov.pdf"}],"publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 72–83.","chicago":"Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 72–83. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>.","apa":"Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., &#38; Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 72–83). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>","mla":"Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 72–83, doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>.","ista":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.","ama":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring G-colourable graphs. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:72-83. doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>","ieee":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of 4-colouring G-colourable graphs,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 72–83."},"ec_funded":1,"publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"corr_author":"1","abstract":[{"lang":"eng","text":"We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory."}],"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_published":"2025-06-15T00:00:00Z","date_updated":"2026-04-07T12:36:50Z","publication_status":"published","project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","grant_number":"P31312"},{"grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"title":"Hardness of 4-colouring G-colourable graphs","department":[{"_id":"UlWa"}],"has_accepted_license":"1","article_processing_charge":"Yes (in subscription journal)","day":"15","publisher":"Association for Computing Machinery","page":"72-83","license":"https://creativecommons.org/licenses/by/4.0/","language":[{"iso":"eng"}],"year":"2025","OA_type":"hybrid","oa_version":"Published Version","status":"public","_id":"20008","ddc":["000"],"file_date_updated":"2025-07-14T06:42:58Z","month":"06","oa":1,"related_material":{"record":[{"relation":"dissertation_contains","id":"20339","status":"public"}]},"date_created":"2025-07-13T22:01:23Z","author":[{"last_name":"Avvakumov","full_name":"Avvakumov, Sergey","orcid":"0000-0002-7840-5062","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey"},{"first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek","last_name":"Filakovský"},{"id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub","full_name":"Opršal, Jakub","last_name":"Opršal","orcid":"0000-0003-1245-3456"},{"last_name":"Tasinato","full_name":"Tasinato, Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"scopus_import":"1","doi":"10.1145/3717823.3718154"},{"ec_funded":1,"arxiv":1,"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]},"corr_author":"1","quality_controlled":"1","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). 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)."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"isi":1,"external_id":{"arxiv":["2312.12981"],"isi":["001300393400034"]},"date_published":"2024-03-01T00:00:00Z","date_updated":"2026-04-07T12:36:50Z","publication_status":"published","project":[{"call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312"},{"grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2024-03-12","location":"Clermont-Ferrand, France","end_date":"2024-03-14"},"type":"conference","acknowledgement":"Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).","alternative_title":["LIPIcs"],"file":[{"file_id":"15175","file_size":927290,"checksum":"0524d4189fd1ed08989546511343edf3","relation":"main_file","content_type":"application/pdf","file_name":"2024_LIPICs_Filakovsky.pdf","date_created":"2024-03-25T07:44:30Z","creator":"dernst","access_level":"open_access","success":1,"date_updated":"2024-03-25T07:44:30Z"}],"publication":"41st International Symposium on Theoretical Aspects of Computer Science","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","citation":{"short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In <i>41st International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</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.” In <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>.","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.","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,” in <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Clermont-Ferrand, France, 2024, vol. 289.","ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: <i>41st International Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>"},"article_number":"34","status":"public","oa_version":"Published Version","ddc":["510"],"_id":"15168","file_date_updated":"2024-03-25T07:44:30Z","month":"03","oa":1,"related_material":{"record":[{"id":"20339","relation":"dissertation_contains","status":"public"}]},"date_created":"2024-03-24T23:00:59Z","volume":289,"author":[{"full_name":"Filakovský, Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek"},{"full_name":"Nakajima, Tamio Vesa","last_name":"Nakajima","first_name":"Tamio Vesa"},{"full_name":"Opršal, Jakub","last_name":"Opršal","orcid":"0000-0003-1245-3456","id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub"},{"full_name":"Tasinato, Gianluca","last_name":"Tasinato","first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"},{"last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"intvolume":"       289","scopus_import":"1","doi":"10.4230/LIPIcs.STACS.2024.34","department":[{"_id":"UlWa"}],"has_accepted_license":"1","article_processing_charge":"No","day":"01","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"year":"2024"},{"date_updated":"2025-05-14T10:51:32Z","publication_status":"published","title":"Topology and adjunction in promise constraint satisfaction","project":[{"grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"date_published":"2023-01-01T00:00:00Z","external_id":{"isi":["000955000000001"],"arxiv":["2003.11351"]},"isi":1,"quality_controlled":"1","abstract":[{"lang":"eng","text":"he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems."}],"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"arxiv":1,"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Krokhin, A., Opršal, J., Wrochna, M., &#38; Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>","chicago":"Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>.","short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.","ieee":"A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction in promise constraint satisfaction,” <i>SIAM Journal on Computing</i>, vol. 52, no. 1. Society for Industrial and Applied Mathematics, pp. 38–79, 2023.","ama":"Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. 2023;52(1):38-79. doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>","mla":"Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>, vol. 52, no. 1, Society for Industrial and Applied Mathematics, 2023, pp. 38–79, doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>.","ista":"Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79."},"publication":"SIAM Journal on Computing","acknowledgement":"Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Stanislav Živný was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper re\u001eects only the authors’ views and not the views of the ERC or the European Commission. ","type":"journal_article","scopus_import":"1","doi":"10.1137/20m1378223","intvolume":"        52","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2003.11351","open_access":"1"}],"author":[{"first_name":"Andrei","last_name":"Krokhin","full_name":"Krokhin, Andrei"},{"id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub","last_name":"Opršal","full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456"},{"first_name":"Marcin","full_name":"Wrochna, Marcin","last_name":"Wrochna"},{"first_name":"Stanislav","full_name":"Živný, Stanislav","last_name":"Živný"}],"date_created":"2023-02-16T07:03:52Z","volume":52,"oa":1,"month":"01","status":"public","oa_version":"Preprint","_id":"12563","language":[{"iso":"eng"}],"year":"2023","page":"38-79","keyword":["General Mathematics","General Computer Science"],"publisher":"Society for Industrial and Applied Mathematics","article_type":"original","day":"01","issue":"1","article_processing_charge":"No","department":[{"_id":"UlWa"}]},{"arxiv":1,"publication_identifier":{"issn":["2372-3491"]},"abstract":[{"lang":"eng","text":"The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP, has started to gain prominence. In this survey, we explain the importance of promise CSP and highlight many new very interesting features that the study of promise CSP has brought to light. The complexity classification quest for the promise CSP is wide open, and we argue that, despite the promise CSP being more general, this quest is rather more accessible to a wide range of researchers than the dichotomy-led study of the CSP has been."}],"quality_controlled":"1","title":"An invitation to the promise constraint satisfaction problem","publication_status":"published","date_updated":"2022-09-05T08:19:38Z","external_id":{"arxiv":["2208.13538"]},"date_published":"2022-07-01T00:00:00Z","type":"journal_article","publication":"ACM SIGLOG News","citation":{"short":"A. Krokhin, J. Opršal, ACM SIGLOG News 9 (2022) 30–59.","apa":"Krokhin, A., &#38; Opršal, J. (2022). An invitation to the promise constraint satisfaction problem. <i>ACM SIGLOG News</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3559736.3559740\">https://doi.org/10.1145/3559736.3559740</a>","chicago":"Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint Satisfaction Problem.” <i>ACM SIGLOG News</i>. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3559736.3559740\">https://doi.org/10.1145/3559736.3559740</a>.","ista":"Krokhin A, Opršal J. 2022. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News. 9(3), 30–59.","mla":"Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint Satisfaction Problem.” <i>ACM SIGLOG News</i>, vol. 9, no. 3, Association for Computing Machinery, 2022, pp. 30–59, doi:<a href=\"https://doi.org/10.1145/3559736.3559740\">10.1145/3559736.3559740</a>.","ama":"Krokhin A, Opršal J. An invitation to the promise constraint satisfaction problem. <i>ACM SIGLOG News</i>. 2022;9(3):30-59. doi:<a href=\"https://doi.org/10.1145/3559736.3559740\">10.1145/3559736.3559740</a>","ieee":"A. Krokhin and J. Opršal, “An invitation to the promise constraint satisfaction problem,” <i>ACM SIGLOG News</i>, vol. 9, no. 3. Association for Computing Machinery, pp. 30–59, 2022."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11991","status":"public","oa_version":"Preprint","oa":1,"month":"07","author":[{"first_name":"Andrei","last_name":"Krokhin","full_name":"Krokhin, Andrei"},{"orcid":"0000-0003-1245-3456","last_name":"Opršal","full_name":"Opršal, Jakub","first_name":"Jakub","id":"ec596741-c539-11ec-b829-c79322a91242"}],"main_file_link":[{"url":"http://arxiv.org/abs/2208.13538","open_access":"1"}],"volume":9,"date_created":"2022-08-27T11:23:37Z","doi":"10.1145/3559736.3559740","intvolume":"         9","article_processing_charge":"No","department":[{"_id":"UlWa"}],"article_type":"original","publisher":"Association for Computing Machinery","day":"01","issue":"3","page":"30-59","year":"2022","language":[{"iso":"eng"}]}]