  Motivated by the study of greedy algorithms for graph coloring, we introduce
a new graph parameter, which we call weak degeneracy. By definition, every
$d$-degenerate graph is also weakly $d$-degenerate. On the other hand, if $G$
is weakly $d$-degenerate, then $\chi(G) \leq d + 1$ (and, moreover, the same
bound holds for the list-chromatic and even the DP-chromatic number of $G$). It
turns out that several upper bounds in graph coloring theory can be phrased in
terms of weak degeneracy. For example, we show that planar graphs are weakly
$4$-degenerate, which implies Thomassen's famous theorem that planar graphs are
$5$-list-colorable. We also prove a version of Brooks's theorem for weak
degeneracy: a connected graph $G$ of maximum degree $d \geq 3$ is weakly
$(d-1)$-degenerate unless $G \cong K_{d + 1}$. (By contrast, all $d$-regular
graphs have degeneracy $d$.) We actually prove an even stronger result, namely
that for every $d \geq 3$, there is $\epsilon > 0$ such that if $G$ is a graph
of weak degeneracy at least $d$, then either $G$ contains a $(d+1)$-clique or
the maximum average degree of $G$ is at least $d + \epsilon$. Finally, we show
that graphs of maximum degree $d$ and either of girth at least $5$ or of
bounded chromatic number are weakly $(d - \Omega(\sqrt{d}))$-degenerate, which
is best possible up to the value of the implied constant.

Combinatorics