Hardness of 4-Colouring 𝐺-Colourable Graphs
| Authors | |
|---|---|
| Year of publication | 2025 |
| Type | Article in Proceedings |
| Conference | STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing |
| MU Faculty or unit | |
| Citation | |
| web | pdf file with the result |
| Doi | https://doi.org/10.1145/3717823.3718154 |
| Keywords | graph colouring; constraint satisfaction problems; promise problems; topological methods; equivariant cohomology |
| Description | We study the complexity of a class of promise graph homomor- phism problems. For a fixed graph ?? , the ?? -colouring problem is to decide whether a given graph has a homomorphism to ?? . By a result of Hell and NeÅ¡etÅil, this problem is NP-hard for any non- bipartite loop-less graph ?? . Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homo- morphism problems as follows: fix a pair of non-bipartite loop-less graphs ??, ?? such that there is a homomorphism from ?? to ?? , it is NP-hard to distinguish between graphs that are ??-colourable and those that are not ?? -colourable. We confirm this conjecture in the cases when both ?? and ?? are 4-colourable. This is a common gen- eralisation 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. |
| Related projects: |