Weak Degeneracy of Planar Graphs and Locally Planar Graphs Article Swipe

PDF

Related Concepts

Degeneracy (biology) Mathematics Combinatorics Planar graph Degenerate energy levels Planar Planar straight-line graph Discrete mathematics Girth (graph theory) Graph 1-planar graph Chordal graph Computer science Physics Computer graphics (images) Quantum mechanics Biology Bioinformatics

Ming Han , Tao Wang , Jianglin Wu , Huan‐Xiang Zhou , Xuding Zhu ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.37236/11749 · OA: W4388289270

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.