DP-coloring extension of the Alon–Krivelevich–Sudakov conjecture

Let GG be a graph and let H=(L,H)\mathcal{H}=(L,H) be a DP-cover of GG. A proper H\mathcal{H}-coloring selects one color from each L(u)L(u) so that the selected colors form an independent set in HH.

DP-coloring extension of the Alon–Krivelevich–Sudakov conjecture. For every graph FF, there is a constant cF>0c_F>0 such that, if HH is FF-free, has maximum degree d2d\geqslant 2, and

L(u)cFd/logd|L(u)|\geqslant c_Fd/\log d

for every uV(G)u\in V(G), then GG admits a proper H\mathcal{H}-coloring.

This would strengthen the ordinary coloring conjecture by imposing the forbidden-subgraph condition on the DP-cover graph rather than on the base graph. The source presents this stronger form as a conjectural extension, and no resolution is given.

Sources & referencesView supporting material

Primary source

James Anderson, Anton Bernshteyn and Abhishek Dhawan, “Coloring graphs with forbidden bipartite subgraphs”, arXiv:2107.05595 (2022).

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.