According to [Wikipedia][1], a *$k$-core* in a graph is a maximal connected subgraph in which every vertex has degree at least $k$. This is the same as your set $S_k$. 

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until either $S_k=\emptyset$ or there are no such vertices left. 

With regards to $k$-cores in random graphs, one natural place to start might be  the paper [*Size and connectivity of the $k$-core of a random graph*][2] by Tomasz Łuczak.


  [1]: https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#k-Cores
  [2]: http://www.sciencedirect.com/science/article/pii/0012365X9190162U