117 views

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?

1. Both SPECIAL-CLIQUE and SPECIAL-COLOURING are undecidable
2. Only SPECIAL-CLIQUE is in $\mathrm{P}$
3. Only SPECIAL-COLOURING is in $\mathrm{P}$
4. Both SPECIAL-CLIQUE and SPECIAL-COLOURING are in $\mathrm{P}$
5. Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable

1 vote