---
OA_place: publisher
OA_type: hybrid
_id: '20008'
abstract:
- lang: eng
  text: '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.'
acknowledgement: This research was supported by the Austrian Science Fund (FWF project
  P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed
  by the Ministry of Education, Youth and Sports of the Czech Republic. This project
  has also received funding from the European Union’s Horizon 2020 research and innovation
  programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Marek
  full_name: Filakovský, Marek
  id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
  last_name: Filakovský
- first_name: Jakub
  full_name: Opršal, Jakub
  id: ec596741-c539-11ec-b829-c79322a91242
  last_name: Opršal
  orcid: 0000-0003-1245-3456
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring
    G-colourable graphs. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory
    of Computing</i>. Association for Computing Machinery; 2025:72-83. doi:<a href="https://doi.org/10.1145/3717823.3718154">10.1145/3717823.3718154</a>'
  apa: 'Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., &#38; Wagner, U.
    (2025). Hardness of 4-colouring G-colourable graphs. In <i>Proceedings of the
    57th Annual ACM Symposium on Theory of Computing</i> (pp. 72–83). Prague, Czechia:
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3717823.3718154">https://doi.org/10.1145/3717823.3718154</a>'
  chicago: Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and
    Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In <i>Proceedings of
    the 57th Annual ACM Symposium on Theory of Computing</i>, 72–83. Association for
    Computing Machinery, 2025. <a href="https://doi.org/10.1145/3717823.3718154">https://doi.org/10.1145/3717823.3718154</a>.
  ieee: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
    of 4-colouring G-colourable graphs,” in <i>Proceedings of the 57th Annual ACM
    Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 72–83.
  ista: 'Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness
    of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium
    on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.'
  mla: Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” <i>Proceedings
    of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing
    Machinery, 2025, pp. 72–83, doi:<a href="https://doi.org/10.1145/3717823.3718154">10.1145/3717823.3718154</a>.
  short: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings
    of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
    Machinery, 2025, pp. 72–83.
conference:
  end_date: 2025-06-27
  location: Prague, Czechia
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2026-04-07T12:36:50Z
day: '15'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1145/3717823.3718154
ec_funded: 1
file:
- access_level: open_access
  checksum: 2c9ae7ad0102c41124976f4cb5182760
  content_type: application/pdf
  creator: dernst
  date_created: 2025-07-14T06:42:58Z
  date_updated: 2025-07-14T06:42:58Z
  file_id: '20013'
  file_name: 2025_STOC_Avvakumov.pdf
  file_size: 940827
  relation: main_file
  success: 1
file_date_updated: 2025-07-14T06:42:58Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 72-83
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - '9798400715105'
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
  record:
  - id: '20339'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Hardness of 4-colouring G-colourable graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...