list partition

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

\begin{problem} Does there exist a \Def{polynomial time} algorithm which takes as input a graph $G$ and for every vertex $v \in V(G)$ a subset $\ell(v)$ of $\{1,2,3,4\}$, and decides if there exists a partition of $V(G)$ into $\{A_1,A_2,A_3,A_4\}$ so that $v \in A_i$ only if $i \in \ell(v)$ and so that $A_1,A_2$ are independent, $A_4$ is a clique, and there are no edges between $A_1$ and $A_3$? \end{problem}

Keywords: list partition; polynomial algorithm

Syndicate content