Matteo García asks how to randomly sample degeneracy orderings of graphs (start with \(k=1\) and at each step remove a vertex of degree at most \(k\), or increase \(k\) when no such vertex remains): https://cstheory.stackexchange.com/q/41846/95

I think this question deserves more attention. My intuition is that it's hard (for instance it might be \(\#\mathsf{P}\)-complete to count degeneracy orderings of trees) but I don't see how to prove it.