Hardness of 4-Colouring G-Colourable Graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Hardness of 4-Colouring G-Colourable Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Hardness of 4-Colouring G-Colourable Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

<a href="/cs/project/EH22_010%2F0003229" target="_blank" >EH22_010/0003229: MSCAfellow5_MUNI</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing

ISBN

9798400715105

ISSN

0737-8017

e-ISSN

—

Počet stran výsledku

12

Strana od-do

72-83

Název nakladatele

Association for Computing Machinery (ACM)

Místo vydání

New York, NY, USA

Místo konání akce

Praha

Datum konání akce

26. 11. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001595410700008