Neighbour sum distinguishing edge colouring Δ+O(1) bound
Open Problem: $\Delta + O(1)$ bound for neighbour sum distinguishing colourings · arXiv:1804.06104
Status open high confidence
The open problem asks whether the number of colours for a neighbour sum distinguishing edge colouring can be bounded by $\Delta + O(1)$. The best known asymptotic upper bound remains $\Delta + O(\Delta^{1/2})$, due to Przyby\l{}o (arXiv:1703.00406, Random Structures & Algorithms 2015/2017). The stronger Flandrin et al.\ conjecture that $\Delta + 2$ colours suffice also remains open. No paper found after 2020 closes the gap between $\Delta + O(\Delta^{1/2})$ and $\Delta + O(1)$.
Reviewer notes. No follow-up resolving the Delta + O(1) open problem was found. The best known bound Delta + O(Delta^{1/2}) due to Przybylo (arXiv:1703.00406) already predates the 2020 source paper. A 2025 paper (arXiv:2511.01835) studies a quasi-majority variant of neighbour sum distinguishing edge-colourings but does not address the classical Delta + O(1) open problem.
Context
A neighbour sum distinguishing colouring is a proper edge colouring $c$ with colours in $[\Delta+2]$ such that for every edge $uv$, the sum of colours incident to $u$ and that of $v$ are distinct — a strengthening of AVD-colourings conjectured by Flandrin et al. The best known asymptotic bound is $\Delta + O(\Delta^{1/2})$ due to Przybyło. The authors note that neither Hatami's proof for AVD-colourings nor their own entropy compression argument seems adaptable to this setting.
Notes. Stated in running prose without a labelled environment; clearly posed as an open problem by the authors.
Source paper
Progress on the adjacent vertex distinguishing edge colouring conjecture
Gwenaël Joret, William Lochet · 2020-07-22
https://arxiv.org/abs/1804.06104
PDF source