Exponential DP-4-colorings of triangle-free planar graphs

Let GG be a triangle-free planar graph with nn vertices, and let PDP(G,4)P_{DP}(G,4) denote its DP color function. The exponential DP-coloring conjecture. There exists a constant c>1c>1 such that, for every triangle-free planar nn-vertex graph GG,

PDP(G,4)cn.P_{DP}(G,4)\geq c^n.

Triangle-free planar graphs are always 4-choosable and DP-4-colorable, although some are not 3-choosable and hence not DP-3-colorable. The conjecture asks for an exponential lower bound on the number of DP-4-colorings; the source contrasts it with subexponential upper bounds known for the number of 3-colorings.

Sources & referencesView supporting material

Primary source

Samantha L. Dahlberg, Hemanshu Kaul and Jeffrey A. Mudrock, “A Polynomial Method for Counting Colorings of Sparse Graphs”, arXiv:2312.11744 (2024).

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.