Hardness of 4-Colourings G-Colourable Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913787435548672 |
|---|---|
| author | Avvakumov, Sergey Filakovský, Marek Opršal, Jakub Tasinato, Gianluca Wagner, Uli |
| author_facet | Avvakumov, Sergey Filakovský, Marek Opršal, Jakub Tasinato, Gianluca Wagner, Uli |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07592 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hardness of 4-Colourings G-Colourable Graphs Avvakumov, Sergey Filakovský, Marek Opršal, Jakub Tasinato, Gianluca Wagner, Uli Computational Complexity Algebraic Topology Combinatorics 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. |
| title | Hardness of 4-Colourings G-Colourable Graphs |
| topic | Computational Complexity Algebraic Topology Combinatorics |
| url | https://arxiv.org/abs/2504.07592 |