This is the authors' abstract. We don't add key points for this paper.
The weak degeneracy of a graph G is a numerical parameter that was recently introduced by the first two authors with the aim of understanding the power of greedy algorithms for graph coloring. Every d-degenerate graph is weakly d-degenerate, but the converse is not true in general (for example, all connected d-regular graphs except cycles and cliques are weakly $(d-1)$-degenerate). If G is weakly d-degenerate, then the list-chromatic number of G is at most $d+1$, and the same upper bound holds for various other parameters such as the DP-chromatic number and the paint number. Here we rectify a mistake in a paper of the first two authors and give a correct proof that planar graphs are weakly $4$-degenerate, strengthening the famous result of Thomassen that planar graphs are $5$-list-colorable.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Bernshteyn et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: