Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sigma$ form a clique in $G$.
Recall that given an undirected graph $G$, a clique in $G$ is a subset of vertices every two of which are connected by an edge, while a perfect colouring of $G$ with $k$ colours is an assignment of labels from the set $\{1,2, \ldots, k\}$ to the vertices of $G$ such that no two vertices which are adjacent in $G$ receive the same label.
Consider the following problems.
Problem SPECIAL-CLIQUE
INPUT: An undirected graph $G$, a positive integer $k$, and a perfect ordering $\sigma$ of the vertices of $G$.
OUTPUT: Yes, if $G$ has a clique of size at least $k$, No otherwise.
Problem SPECIAL-COLOURING
INPUT: An undirected graph $G$, a positive integer $k$, and a perfect ordering $\sigma$ of the vertices of $G$.
OUTPUT: Yes, if $G$ has a proper colouring with at most $k$ colours, No otherwise.
Assume that $\mathrm{P} \neq N P$. Which of the following statements is true?
- Both SPECIAL-CLIQUE and SPECIAL-COLOURING are undecidable
- Only SPECIAL-CLIQUE is in $\mathrm{P}$
- Only SPECIAL-COLOURING is in $\mathrm{P}$
- Both SPECIAL-CLIQUE and SPECIAL-COLOURING are in $\mathrm{P}$
- Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable
