Cutwidth and degeneracy of graphs

Abstract

We prove an inequality involving the degeneracy, the cutwidth and the sparsity of graphs. It implies a quadratic lower bound on the cutwidth in terms of the degeneracy for all graphs and an improvement of it for clique-free graphs.

v2: slightly shortened, some typos corrected.