Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to  any  polynomial-time recognizable graph class? To avoid degenerated cases, let us consider only  dense  graph classes, in which   the number of non-isomorphic $\leq n$-vertex graphs grows exponentially with $n$. Notes:  (1) Both a yes or a no answer would be quite interesting. If the answer is yes, then we would have a natural  $\mathsf{NP}$-complete graph property that could be called  universally hard,  because it preserves hardness even when  restricted to any reasonable graph class.  If the answer is no, it would mean that every natural $\mathsf{NP}$-complete graph property can be made easy on some nontrivial graph class. (2) It is important to consider only polynomial-time recognizable graph classes, to exclude that the hardness of the property is simply shifted to the class.For example, 3-COLORABILITY becomes trivial when restricted  to 3-colorable graphs.
Can a natural graph problem be universally hard?
cc.complexity theory;graph theory;graph algorithms;np complete;graph classes
The definition of natural is a bit fuzzy, but there's a trivial reason the answer here is likely no. Suppose to the contrary that there is such a problem, $P$. If $P$ only acts on the first component of the provided graph, then $P$ is easy on the class of graphs where the first component is an instance of $P$ and the second component encodes a certificate of $P$ holding on the first component. Further, this class of graphs is polytime recognizable. Indeed, the same holds true if we can designate a portion of the graph as a this is a certificate and not part of the problem component, in the sense that we can sneak this certificate in without affecting the true answer. Most natural problems, as far as I can tell, allow for the designation of such a piece of the graph. Here are a few examplesMax Clique: just ensure that the certificate portion of the graph does not have a large clique (eg. encode it using a matching)Hamiltonian Path: the tail node is replaced by a certificate graph which has an easy-to-find Hamiltonian path of its ownHamiltonian Circuit: same as Hamiltonian path except some designated vertex is replaced with a certificate graph containing a Hamiltonian cycleMax Cut: this doesn't affect the solution as long as there are no edges to the rest of the graph, so we just ensure that the max cut here is easy to find (eg. we encode using a matching)Vertex cover: the certificate is again encoded by a matchingWe ensure that the certificate portion of the graph is designated as such, so to not lose it in the rest of the graph (though designating them implicitly via the graph structure is probably easy enough for most natural problems).Since NP-complete problems cannot be sparse unless $P=NP$ (Mahaney's theorem), neither can this construction, satisfying your non-triviality constraint.