2024/06/04 by Bernshteyn, Anton, Lee, Eugene, Smith-Roberge, Evelyne
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2406.02792
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.