Topology and adjunction in promise constraint satisfaction

Andrei Krokhin, Jakub Opršal, Marcin Wrochna +1

The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a $c$-colouring of a graph that is promised to be $k$-colourable, where $c\g…