Is the minimal number of colors needed to color a graph some fixed number?

Question

Consider to following decision problem:

Input: Undirected graph $G=(V,E)$

Question: Is the minimum numbers of colors needed to color the vertices (such that every two adjacent vertices aren't colored the same) exactly 2015?

Note that 2015 could be any fixed number. This number is not part of the input.

I need to understand what is the minimal complexity class that contain this problem, between $\sf P,NP,coNP,NP\cup coNP,\Sigma _{2} \cap \Pi _{2}, \Sigma _{2} \cup \Pi _{2}$.

I don't it's $\sf NP$ or $\sf coNP$ since I can't think of a verifier for both the language or it's complement. The problem is maybe in $\sf \Sigma _{2} \cap \Pi {2}$ since we can think of it as

exists $f$ some 2009-coloring function, for-all $g$, 2008-coloring function, $f$ is a correct coloring and $g$ isn't a correct coloring.

So by the above, it seems that the language is in $\sf \Sigma _{2}$, but the quantifiers order doesn't really matter here, so the language is also in $\sf \Pi _{2}$, I think.

And maybe the there is some deterministic polynomial-time algorithm?

Answer 1

The problem is always in $\Delta_2 = \Sigma_2 \cap \Pi_2$, as you mention. For some values of 2015 it is easier: deciding whether a graph has chromatic number 3 is NP-complete, and deciding whether a graph has chromatic number 2 or 1 is in P (since you can check whether a graph is bipartite in polytime).

Since deciding whether a graph has chromatic number 3 is NP-hard, so is deciding whether it has chromatic number 2015, by reduction: add a clique of size 2012, and connect it to all vertices; this increases the chromatic number by exactly 2012. So there is no hope for a polynomial time algorithm.