Dark Mode

117 views

1 vote

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