
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.
Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, weakly \(d\)-degenerate graphs, Combinatorics (math.CO), greedy coloring algorithm, Planar graphs; geometric and topological aspects of graph theory, 05C10
Coloring of graphs and hypergraphs, FOS: Mathematics, Mathematics - Combinatorics, weakly \(d\)-degenerate graphs, Combinatorics (math.CO), greedy coloring algorithm, Planar graphs; geometric and topological aspects of graph theory, 05C10
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
