2023/03/14 by Ming Han, Tao Wang, Han, Ming +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2303.07901
Weak degeneracy is a variation of degeneracy which shares many nice properties of degeneracy. In particular, if a graph G is weakly d-degenerate, then for any (d + 1)-list assignment L of G, one can construct an L-coloring of G by a modified greedy coloring algorithm. It is known that planar graphs of girth 5 are 3-choosable and locally planar graphs are 5-choosable. This paper strengthens these results and proves that planar graphs of girth 5 are weakly 2-degenerate and locally planar graphs are weakly 4-degenerate.