Exponential average-availability conjecture for local girth in planar graphs
Exponential average-availability conjecture for local girth in planar graphs
Let be a planar graph and let be a local girth function for . For an operation sequence , define its average availability by
where the availability of is and the availability of is . A sequence is legal if each operation is legal, and it removes every vertex when it certifies weak -degeneracy.
Exponential average-availability conjecture. There exists a constant such that, for every planar graph and local girth function for , there is a legal sequence of operations with average availability at least that removes every vertex of .
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 , hence at least . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.