Exponential DP-4-colorings of triangle-free planar graphs
Exponential DP-4-colorings of triangle-free planar graphs
Let be a triangle-free planar graph with vertices, and let denote its DP color function. The exponential DP-coloring conjecture. There exists a constant such that, for every triangle-free planar -vertex graph ,
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
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.