A graph $G=(V, E)$ is said to be $k$-colourable if the set $V$ of vertices can be coloured with $k$ colours such that no edge has both its endpoints of the same colour. It is known that the following language $\text{3COL}$ is $\text{NP}$-complete.
\[
3 \mathrm{COL}=\{G \mid G \text { is 3-colourable }\} .
\]
Consider the following algorithmic problems (assume that the input graph $G$ is provided as its adjacency matrix):
$\text{(P1)}$ Given a graph $G$ as input, check if $G$ is $2$-colourable.
$\text{(P2)}$ Given a graph $G$ as input, find the minimum value of $k$ such that $G$ is $k$-colourable.
$\text{(P3)}$ Given a graph $G$, check if $G$ is $3$-colourable.
$\text{(P4)}$ Given a graph $G$, along with a guarantee that the minimum value of $k$ such that $G$ is $k$-colourable is either $2$ or $3,$ decide which of the two is the case.
Assume $\mathrm{NP} \neq \mathrm{P}$. Then, which of the above problems can be solved in polynomial time?
- Only problem $\text{(P1)}$
- Only problems $\text{(P1)}$ and $\text{(P4)}$
- Only problems $\text{(P2)}$ and $\text{(P3)}$
- Only problems $\text{(P1), (P3)}$and $\text{(P4)}$
- Only problems $\text{(P1), (P2)}$and $\text{(P4)}$
