DP-coloring extension of the Alon–Krivelevich–Sudakov conjecture
DP-coloring extension of the Alon–Krivelevich–Sudakov conjecture
Let be a graph and let be a DP-cover of . A proper -coloring selects one color from each so that the selected colors form an independent set in .
DP-coloring extension of the Alon–Krivelevich–Sudakov conjecture. For every graph , there is a constant such that, if is -free, has maximum degree , and
for every , then admits a proper -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
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.