Hardness of 4-Colouring G-Colourable Graphs

D 2025

Hardness of 4-Colouring G-Colourable Graphs

FILAKOVSKÝ, Marek; Sergey AVVAKUMOV; Jakub OPRŠAL; Gianluca TASINATO; Uli WAGNER et al.

Základní údaje

Originální název

Hardness of 4-Colouring G-Colourable Graphs

Autoři

FILAKOVSKÝ, Marek; Sergey AVVAKUMOV; Jakub OPRŠAL; Gianluca TASINATO a Uli WAGNER

Vydání

New York, NY, USA, STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, od s. 72-83, 12 s. 2025

Nakladatel

Association for Computing Machinery (ACM)

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10100 1.1 Mathematics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

pdf file with the result

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00140144

Organizační jednotka

Fakulta informatiky

ISBN

979-8-4007-1510-5

ISSN

Klíčová slova anglicky

graph colouring; constraint satisfaction problems; promise problems; topological methods; equivariant cohomology

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 9. 4. 2026 15:07, Mgr. Petra Trembecká, Ph.D.

Anotace

V originále

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

CZ.02.01.01/00/22_010/0003229, interní kód MU
(Kód CEP: EH22_010/0003229)

Název: MSCAfellow5_MUNI

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, MSCAfellow5_MUNI, Priorita 1 - Výzkum a vývoj

EH22_010/0003229, projekt VaV

Název: MSCAfellow5_MUNI

Citovat

FILAKOVSKÝ, Marek; Sergey AVVAKUMOV; Jakub OPRŠAL; Gianluca TASINATO a Uli WAGNER. Hardness of 4-Colouring G-Colourable Graphs. Online. In STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. New York, NY, USA: Association for Computing Machinery (ACM), 2025, s. 72-83. ISBN 979-8-4007-1510-5. Dostupné z: https://doi.org/10.1145/3717823.3718154.

@inproceedings{2535860,
   author = {Filakovský, Marek and Avvakumov, Sergey and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli},
   address = {New York, NY, USA},
   booktitle = {STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing},
   doi = {https://doi.org/10.1145/3717823.3718154},
   keywords = {graph colouring; constraint satisfaction problems; promise problems; topological methods; equivariant cohomology},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {New York, NY, USA},
   isbn = {979-8-4007-1510-5},
   pages = {72-83},
   publisher = {Association for Computing Machinery (ACM)},
   title = {Hardness of 4-Colouring G-Colourable Graphs},
   url = {https://dl.acm.org/doi/pdf/10.1145/3717823.3718154},
   year = {2025}
}

TY  - CONF
ID  - 2535860
AU  - Filakovský, Marek - Avvakumov, Sergey - Opršal, Jakub - Tasinato, Gianluca - Wagner, Uli
PY  - 2025
TI  - Hardness of 4-Colouring G-Colourable Graphs
PB  - Association for Computing Machinery (ACM)
CY  - New York, NY, USA
SN  - 9798400715105
KW  - graph colouring
KW  - constraint satisfaction problems
KW  - promise problems
KW  - topological methods
KW  - equivariant cohomology
UR  - https://dl.acm.org/doi/pdf/10.1145/3717823.3718154
N2  - 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.
ER  -

FILAKOVSKÝ, Marek; Sergey AVVAKUMOV; Jakub OPRŠAL; Gianluca TASINATO a Uli WAGNER. Hardness of 4-Colouring G-Colourable Graphs. Online. In \textit{STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing}. New York, NY, USA: Association for Computing Machinery (ACM), 2025, s.~72-83. ISBN~979-8-4007-1510-5. Dostupné z: https://doi.org/10.1145/3717823.3718154.

Přehled o publikaci