Cambie–Kang conjecture for triangle-free DP-coloring

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 chooses one color from each L(v)L(v) so that the chosen colors are independent in HH.

Cambie–Kang conjecture. For every ε>0\varepsilon>0, there is d0Nd_0\in\mathbb{N} such that, if HH has maximum degree dd0d\geqslant d_0 and

L(v)(1+ε)d/logd|L(v)|\geqslant (1+\varepsilon)d/\log d

for every vV(G)v\in V(G), then GG admits a proper H\mathcal{H}-coloring provided either GG is triangle-free (weak version) or HH is triangle-free (strong version).

The conjecture asks whether the constant 4+o(1)4+o(1) can be reduced to 1+o(1)1+o(1), and the source explicitly describes it as open, even in the list-coloring framework.

Sources & referencesView supporting material

Primary source

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

Additional references

2 papers in this index state this conjecture (2021–2022). The statement above is taken from the most recent of them; the others are arXiv:2107.05595.

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.