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

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?

• That problem is in DP. ​ ​
– user12859
Jan 10, 2016 at 12:31

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).