Hardness of 4-colouring G-colourable graphs
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.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Corresponding author has ISTA affiliation
Department
Abstract
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.
Publishing Year
Date Published
2025-06-15
Proceedings Title
Proceedings of the 57th Annual ACM Symposium on Theory of Computing
Publisher
Association for Computing Machinery
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.
Page
72-83
Conference
STOC: Symposium on Theory of Computing
Conference Location
Prague, Czechia
Conference Date
2025-06-23 – 2025-06-27
ISBN
ISSN
IST-REx-ID
Cite this
Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring G-colourable graphs. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2025:72-83. doi:10.1145/3717823.3718154
Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., & Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 72–83). Prague, Czechia: Association for Computing Machinery. https://doi.org/10.1145/3717823.3718154
Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 72–83. Association for Computing Machinery, 2025. https://doi.org/10.1145/3717823.3718154.
S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of 4-colouring G-colourable graphs,” in Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Prague, Czechia, 2025, pp. 72–83.
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, et al. “Hardness of 4-Colouring G-Colourable Graphs.” Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 72–83, doi:10.1145/3717823.3718154.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2025_STOC_Avvakumov.pdf
940.83 KB
Access Level
Open Access
Date Uploaded
2025-07-14
MD5 Checksum
2c9ae7ad0102c41124976f4cb5182760
Google Scholar
ISBN Search