Why is χ(G) NP-Hard and not NP-Complete

Question

Where I got my Info <- May want to fact check me

So given that deciding whether a graph with N vertices is colorable with K colors is NP-Complete, and focusing on the case where this can be determined in polynomial time, and knowing upper and lower bounds of χ(G) being, not including much optimizations, an integer from 1 to K (Can be derived from Brook's Theorem + you can't have half a color).

Don't we already have methods of finding a integer between 1 to K in $\lceil\log_{2}\left(K\right)\rceil$ guesses? Meaning that if deciding a graph can be done in polynomial time ( $O\left(K^{c}\right)$ ), then couldn't the $O$ of χ(G) be $\lceil\log_{2}\left(K\right)\rceil*O\left(K^{c}\right)$, simplifying to $O\left(K^{c}\right)$, meaning that χ(G) is NP-Complete?

EDIT: Actually, so can't we confirm it in polynomial time too just by showing that showing that for A, where A is the chromatic number, and show that A-1 colors can't color the graph & A colors can color the graph in NP-Complete time (because it's just the Deciding stuff above), then if P = NP then we can check this in polynomial time? Along with the case of P $\neq$ NP, then χ(G) is NP-Complete?

While this isn't confirming it's the answer in polynomial time exactly, if P vs Np is true, then it would be polynomial time, else it's not polynomial

---So if P=NP, then χ(G) is NP-Complete which along with the previous statement, makes χ(G) is P. If P /= NP, then χ(G) is NP-Hard, meaning that χ(G) is NP. This just seems like a double layered NP-Complete now.

I apologize for any overlooks I may have taken, this is just a thought I had and needed to get out. EDIT- Ok that may have been confusing.

Answer 1

A $\mathcal{NP}$-complete problem is by definition a decision problem (the answer is true of false). For example, given $k$, deciding if a graph is $k$-colorable is $\mathcal{NP}$-complete.

An optimization problem, like computing $\chi(G)$ can't be $\mathcal{NP}$-complete, because this expected answer is a number, not true/false.

However, you are right that we can query $\chi(G)$ with a polynomial number of oracles to the $k$-coloring problem, but it does not make $\chi(G)$ $\mathcal{NP}$-complete. This result is more general. For a given optimization problem, if its decision problem is $NP$-complete and that the objective function is computable in polynomial time, you can solve it in polynomial time using a polynomial number of oracle to the decision problem with binary search.

Answer 2

All NP-Complete problems are also NP-Hard. In particular graph coloring is both NP-Hard and NP-Complete. I am having a bit of trouble understanding your argument in the second half of your question. In order to argue that something is NP-Complete, we just need NP-Hardness and a verification certificate which can be checked in polynomial time. In this case, a k-coloring of the graph would suffice for the certificate as that could be checked in polynomial time. There is no need to try to guess k, as that is given to us as input.