Weak degeneracy of planar graphs and locally planar graphs (Q6117236): Difference between revisions

Summary: 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.