Hardness of 4-Colouring G-Colourable Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00140144" target="_blank" >RIV/00216224:14330/25:00140144 - isvavai.cz</a>
Result on the web
<a href="https://dl.acm.org/doi/pdf/10.1145/3717823.3718154" target="_blank" >https://dl.acm.org/doi/pdf/10.1145/3717823.3718154</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3717823.3718154" target="_blank" >10.1145/3717823.3718154</a>
Alternative languages
Result language
angličtina
Original language name
Hardness of 4-Colouring G-Colourable Graphs
Original language 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10100 - Mathematics
Result continuities
Project
<a href="/en/project/EH22_010%2F0003229" target="_blank" >EH22_010/0003229: MSCAfellow5_MUNI</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
ISBN
9798400715105
ISSN
0737-8017
e-ISSN
—
Number of pages
12
Pages from-to
72-83
Publisher name
Association for Computing Machinery (ACM)
Place of publication
New York, NY, USA
Event location
Praha
Event date
Nov 26, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001595410700008