conference paper published yes Sergey Avvakumov author 3827DAC8-F248-11E8-B48F-1D18A9856A870000-0002-7840-5062 Marek Filakovský author 3E8AF77E-F248-11E8-B48F-1D18A9856A87 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 STOC: Symposium on Theory of Computing Algorithms for Embeddings and Homotopy Theory project IST-BRIDGE: International postdoctoral program project 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. https://research-explorer.ista.ac.at/download/20008/20013/2025_STOC_Avvakumov.pdf application/pdfno Association for Computing Machinery2025Prague, Czechia eng 0737-8017 979840071510510.1145/3717823.3718154 72-83 https://research-explorer.ista.ac.at/record/20339 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. 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. 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> 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> 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. 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>. 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>. 200082025-07-13T22:01:23Z2026-07-29T13:13:17Z