Informace o publikaci
Hardness of 4-Colouring 𝐺-Colourable Graphs
| Autoři | |
|---|---|
| Rok publikování | 2025 |
| Druh | Článek ve sborníku |
| Konference | STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | pdf file with the result |
| Doi | https://doi.org/10.1145/3717823.3718154 |
| Klíčová slova | graph colouring; constraint satisfaction problems; promise problems; topological methods; equivariant cohomology |
| Popis | 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. |
| Související projekty: |