← All problems

Proper conflict-free (degree+2)-choosability conjecture

Every connected graph GG other than the 55-cycle C5C_5 is proper conflict-free (degree+2)(\mathrm{degree}+2)-choosable; that is, for every list assignment LL satisfying ∣L(v)∣≥dG(v)+2|L(v)|\ge d_G(v)+2 for all v∈V(G)v\in V(G), there exists a coloring φ\varphi such that φ(v)∈L(v)\varphi(v)\in L(v) for every vv, φ(u)≠φ(v)\varphi(u)\ne\varphi(v) whenever uv∈E(G)uv\in E(G), and for every non-isolated vertex vv there is a color cc with ∣{u∈NG(v):φ(u)=c}∣=1|\{u\in N_G(v):\varphi(u)=c\}|=1.

References

Progress summary

Refreshed
Open · progress reported

Recent papers improve the conjecture for broader classes of sparse graphs, but the general statement remains open.

The conjecture asserts that every connected graph other than C5C_5 is proper conflict-free (degree+2)(\mathrm{degree}+2)-choosable. The full characterization has not been proved.

Known results

  • Connected subcubic graphs and connected outerplanar graphs other than C5C_5 satisfy the conjecture.
  • Wang and Zhang (2025) proved it for connected K4K_4-minor-free graphs with maximum degree at most 44, outer-11-planar graphs with maximum degree at most 44, and planar graphs of girth at least 1212.
  • Lu et al. (2026) obtained a bounded-average-degree result, including connected graphs other than C5C_5 with mad⁡(G)<12/5\operatorname{mad}(G)<12/5.

October 2026 bounded-average-degree improvement

Huijuan Xu reports proper conflict-free (degree+2)(\mathrm{degree}+2)-choosability for graphs with maximum average degree less than 8/38/3, with planar graphs of girth at least 88 among the consequences. This is progress on restricted classes, not a resolution of the full conjecture, and the claim has not been independently verified here.

Current status (as of November 2026): The conjecture is open in general; several sparse graph classes are settled, while the October 2026 bounded-average-degree advance remains an unverified partial result.

Sources

Solutions 0

No solutions have been posted yet.