Every planar graph is weakly degenerate with list sizes f(v) ≥ max{7-g(v),2}, proving the correspondence-colouring analogue of local-girth choosability.
Weak degeneracy of planar graphs and locally planar graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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.
fields
math.CO 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Local Weak Degeneracy of Planar Graphs
Every planar graph is weakly degenerate with list sizes f(v) ≥ max{7-g(v),2}, proving the correspondence-colouring analogue of local-girth choosability.