Hardness of 4-Colouring G-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 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 homo- morphism 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 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: |