Is a graph at least k-colorable? (Complexity)


Well, all graphs are colorable with $geq k$ colors: Assign each vertex a different color (and leave the other color classes empty if $k$ is larger than the number of vertices of the given graph).

As for the complement of this problem, note that you did not correctly invert the definition of the problem:
A problem $L$ is, after all, merely a set of strings over some finite alphabet $Sigma$ representing some objects with some property.
Its complement is then the set $Sigma^ast setminus L$ or the set of all strings not representing an object with the property.
If we recall the argument above, we find that the complement of your problem is hence the set of all strings not representing graphs (under that fixed encoding scheme) rather than the one you claimed. This problem (as the first one), is in $mathsf P$.