Exponential average-availability conjecture for local girth in planar graphs

Let GG be a planar graph and let ff be a local girth function for GG. For an operation sequence σ\sigma, define its average availability by

a(σ)=i=1na(σi)1/n,\overline a(\sigma)=\prod_{i=1}^n a(\sigma_i)^{1/n},

where the availability of Del(G,f,v)\mathsf{Del}(G,f,v) is f(v)+1f(v)+1 and the availability of DelSave(G,f,v,w)\mathsf{DelSave}(G,f,v,w) is f(v)f(w)f(v)-f(w). A sequence is legal if each operation is legal, and it removes every vertex when it certifies weak ff-degeneracy.

Exponential average-availability conjecture. There exists a constant c>1c>1 such that, for every planar graph GG and local girth function ff for GG, there is a legal sequence of operations σ\sigma with average availability at least cc that removes every vertex of GG.

Together with the proposition preceding the conjecture, this would yield exponentially many local-girth correspondence colourings of planar graphs: the number of colourings would be at least a(σ)v(G)\overline a(\sigma)^{v(G)}, hence at least cv(G)c^{v(G)}. The supplied text gives no evidence that the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Ewan Davies and Evelyne Smith-Roberge, “Local Weak Degeneracy of Planar Graphs”, arXiv:2504.21821 (2025).

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.