Weak Degeneracy of Planar Graphs

ABSTRACT The weak degeneracy of a graph 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 ‐degenerate graph is weakly ‐degenerate, but the converse is not true in general (e.g., all connected ‐regular graphs except cycles and cliques are weakly ‐degenerate). If is weakly ‐degenerate, then the list‐chromatic number of is at most , 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.