@inproceedings{20008,
  abstract     = {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.},
  author       = {Avvakumov, Sergey and Filakovský, Marek and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli},
  booktitle    = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing},
  isbn         = {9798400715105},
  issn         = {0737-8017},
  location     = {Prague, Czechia},
  pages        = {72--83},
  publisher    = {Association for Computing Machinery},
  title        = {{Hardness of 4-colouring G-colourable graphs}},
  doi          = {10.1145/3717823.3718154},
  year         = {2025},
}

@inproceedings{15168,
  abstract     = {A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).},
  author       = {Filakovský, Marek and Nakajima, Tamio Vesa and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli},
  booktitle    = {41st International Symposium on Theoretical Aspects of Computer Science},
  isbn         = {9783959773119},
  issn         = {1868-8969},
  location     = {Clermont-Ferrand, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs}},
  doi          = {10.4230/LIPIcs.STACS.2024.34},
  volume       = {289},
  year         = {2024},
}

@article{12563,
  abstract     = {he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.},
  author       = {Krokhin, Andrei and Opršal, Jakub and Wrochna, Marcin and Živný, Stanislav},
  issn         = {1095-7111},
  journal      = {SIAM Journal on Computing},
  keywords     = {General Mathematics, General Computer Science},
  number       = {1},
  pages        = {38--79},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Topology and adjunction in promise constraint satisfaction}},
  doi          = {10.1137/20m1378223},
  volume       = {52},
  year         = {2023},
}

@article{11991,
  abstract     = {The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP, has started to gain prominence. In this survey, we explain the importance of promise CSP and highlight many new very interesting features that the study of promise CSP has brought to light. The complexity classification quest for the promise CSP is wide open, and we argue that, despite the promise CSP being more general, this quest is rather more accessible to a wide range of researchers than the dichotomy-led study of the CSP has been.},
  author       = {Krokhin, Andrei and Opršal, Jakub},
  issn         = {2372-3491},
  journal      = {ACM SIGLOG News},
  number       = {3},
  pages        = {30--59},
  publisher    = {Association for Computing Machinery},
  title        = {{An invitation to the promise constraint satisfaction problem}},
  doi          = {10.1145/3559736.3559740},
  volume       = {9},
  year         = {2022},
}