Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in cubic bipartite Hamiltonian graphs. Maximum independent set is not in $APX$ unless $P=NP$ but it is in $APX$ for cubic graphs. David Eppstein pointed out that it is $NP$-complete to find maximum clique in claw-free graphs and it is not clear to me if it is any easier to approximate than in general graphs.
- I'm interested in optimization problems that remains in-approximable in severely restricted classes of graphs (for instance, cubic planar bipartite graphs or trees of bounded degree).
A problem $L$ is In-approximable means that $L \notin APX$. It is $NP$-hard to approximate to any constant factor in polynomial-time.