Follow

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): cstheory.stackexchange.com/q/4

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.

Sign in to participate in the conversation
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes.

Use \( and \) for inline LaTeX, and \[ and \] for display mode.