$\textbf{(P1):}$ Given a graph $G$, check if $G$ is 2-colourable.
A graph will be 2-colourable $\iff$ it is bipartite.
We can test bipartiteness in polynomial time using BFS.
So $\textbf{(P1)}$ is solvable in polynomial time.
Algorithm
$\textbf{(P2):}$ Given a graph $G$, find the minimum $k$ such that $G$ is $k$-colourable.
If we could solve this in polynomial time, we could decide 3-colourability by checking whether $\chi(G) \le 3$ which just contradicts the assumption $\text{P} \ne \text{NP}$.
So $\textbf{(P2)}$ is not solvable in polynomial time.
$\textbf{(P3):}$ Given a graph $G$, check if $G$ is 3-colourable.
This is the $3\text{-COL}$ problem, which is NP-complete.
So $\textbf{(P3)}$ is not solvable in polynomial time.
$\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.
We can apply a simple algorithm to solve this problem:
Check if $G$ is $2$-colourable.which is decidable in polynomial time
If $G$ is $2$-colourable $\Rightarrow$ $\chi(G) = 2$
If $G$ is not $2$-colourable and since $\chi(G)$ is either $2$ or $3$, it must be $3$.
So $\textbf{(P4)}$ is solvable in polynomial time.
\[
\boxed{\text{B. Only problems (P1) and (P4)}}
\]
