12 problems

A promise CSP is specified by relational structures $(B,C)$ with a homomorphism from $B$ to $C$; $\operatorname{PCSP}(B,C)$ asks whether an input finite structure $A$ has a homomor…

Let $K_\ell$ denote the clique with $\ell$ vertices. For integers $n$ and $m$ satisfying … consider the promise constraint satisfaction problem $\operatorname{PCSP}(K_n,K_m)$, whic…

A linearly-ordered colouring of a hypergraph assigns linearly ordered colours to its vertices so that the maximum colour in every hyperedge is unique. For positive integers…

For integers $k\geq c\geq 2$, let $\operatorname{LO}_c$ and $\operatorname{LO}_k$ denote the relational structures whose ternary relation encodes linearly ordered $c$-colouring and…

For integers $k\geq l\geq 3$, $\operatorname{PCSP}(K_l,K_k)$ is the promise problem of coloring a graph with $k$ colors under the promise that it is $l$-colorable. Promise-coloring…

Promise Hell–Nešetřil dichotomy conjecture. The problem

Approximate graph-colouring conjecture. For any fixed integers $3\leq k\leq c$, this problem is NP-hard.

Bulatov–Grohe conjecture. Every tractable finite-domain $\operatorname{PCSP}$ is solved by a tractable test.

Let $r$ and $s$ be integers with $3\leq r\leq s$, and let $\mathbf{K}_r$ and $\mathbf{K}_s$ denote the complete graphs on $r$ and $s$ vertices, respectively. The promise problem…

Brakensiek–Guruswami conjecture. For any non-bipartite loopless graphs $\rel H$ and $\rel G$ with $\rel H\to\rel G$, the problem

Let $k,c\geq 2$. Define $A$ to be the relational structure on $E_{k+1}$ whose relation consists of the $k$-tuples with pairwise distinct entries, and define $B$ to be the relationa…

Fix integers $3\leq k\leq c$. Let $E_k$ and $E_c$ be colour sets of sizes $k$ and $c$, respectively, and let $\ne_k$ and $\ne_c$ be the corresponding disequality relations. The pro…