The approximate graph colouring problem concerns colouring a $k$-colourable
graph with $c$ colours, where $c\geq k$. This problem naturally generalises
to promise graph homomorphism and further to promise constraint satisfaction
problems. Complexity analysis of all these problems is notoriously difficult.
In this paper, we introduce ... more >>>

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>