Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?

Question

For an undirected graph $G$, let us denote $\gamma(G)$ the chromatic number of $G$. Let us define for positive integer $n$, the language $$ L_n = \{\langle G\rangle : \gamma(G) = n\}. $$ This is the language of undirected graphs with chromatic number $n$. I think $L_n \in \mathrm{P}^{\mathrm{NP}}$, for any $n$.

My argument is the following. We can look at the language, $$ \mathrm{CHROMNUM} = \{\langle G, k\rangle : \gamma(G) \leq k\}. $$ It is clear that $\mathrm{CHROMNUM} \in \mathrm{NP}$, since we can verify an instance just by displaying an at most $k$-coloring of $G$.

Thus, consider oracle Turing machine $M^{\mathrm{CHROMNUM}}_n$, which on input $G$, simply checks that $\langle G, n \rangle \in \mathrm{CHROMNUM}$ and that $\langle G, k \rangle \not \in \mathrm{CHROMNUM}$ for all $k \leq n$.

I've just read about $\mathrm{P}^{\mathrm{NP}}$, so I wanted to be sure that this kind of argument is correct.

Answer 1

Yes, your argument is correct.

$\textbf{P}^\textbf{NP}$ is the class of problems which are Cook-reducible (i.e., polynomial-time Turing-reducible) to $\textbf{NP}$. A Turing reduction to $\textbf{NP}$ is simply a reduction with oracle access to a problem in $\textbf{NP}$, in this case the problem $\text{CHROMNUM}$.

In fact, using your reasoning and the fact that $\langle G, k \rangle \not\in \text{CHROMNUM} \implies \langle G, k' \rangle \not\in \text{CHROMNUM}$ for all $k' \le k$, you can prove that you only need two oracle queries (independent of $n$). That is, your reduction resumes to checking the following: $$\langle G, n \rangle \in \text{CHROMNUM} \land \langle G, n - 1 \rangle \not\in \text{CHROMNUM}$$ This means you only need one $\textbf{NP}$ query and one $\textbf{coNP}$ query (since checking if something is not in an $\textbf{NP}$ language is in $\textbf{coNP}$). As it turns out, there is a class of problems which are characterized by having the same type of reduction, the difference polynomial time class $\textbf{D}^\textbf{P}$, and which, incidentally, coincides with the second level of the Boolean hierarchy.