I am new to the complexity theory and I am trying to understand what would be the complexity of the following problem: "Is a graph AT LEAST $k$-colorable?"
Whether a graph is $k$-colorable is clearly a NPC problem and is explained by reduction to 3-SAT.
However, I am not sure to which complexity class belongs the modified problem I have stated. Does it belong to NP as well? My guess is that we would be able to check it with a polynomial certificate (any $\geq k$ coloring of the graph).
And then the problem "Is a graph AT MOST $k$-colorable?" would be its complement in co-NP unless NP=co-NP?