Maybe there is a trivial answer to my question or maybe there is not any. But I ask it here and appreciate if anyone can give me a clear answer.
We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but maybe polynomial-time solvable for specific graphs.
My question is that, if we are given a graph $G=(V,E)$ (I am asking this generally but you can specifically assume the graph described here), and want to find for example minimum clique cover for this graph, how can we show that it is NP-hard (if it is)? Is there any method for that?