2023/09/22 by Yang, Yuxuan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.12670
Motivated by the study of greedy algorithms for graph coloring, Bernshteyn and Lee introduced a generalization of graph degeneracy, which is called weak degeneracy. In this paper, we show the lower bound of the weak degeneracy for d-regular graphs is exactly \lfloor d/2\rfloor +1, which is tight. This result refutes the conjecture of Bernshteyn and Lee on this lower bound.