Bernshteyn–Lee's lower-bound conjecture for weak degeneracy of regular graphs

A graph GG is weakly dd-degenerate if it is weakly ff-degenerate for the constant function with value dd, and its weak degeneracy wd(G)\operatorname{wd}(G) is the minimum such integer dd. Bernshteyn–Lee's conjecture. Every dd-regular graph GG satisfies

wd(G)dO(d).\operatorname{wd}(G)\geqslant d-O(\sqrt{d}).

The conjecture would improve the general lower bound wd(G)d2n\operatorname{wd}(G)\geqslant d-\sqrt{2n} for a dd-regular graph with n2n\geqslant2 vertices, showing that weak degeneracy is close to the degree independently of the graph's order. The trivial upper bound is dd, attained by complete graphs.

Sources & referencesView supporting material

Primary source

Yuxuan Yang, “Weak degeneracy of regular graphs”, arXiv:2309.12670 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.