Probabilistic barrier for adjacent distinguishing Δ+2

Informal Conjecture: probabilistic methods insufficient for the $\Delta+2$ bound · arXiv:1804.06104

arXiv Informal medium confidence— first stated 2020-07-22

Authors: Gwenaël Joret, William Lochet

Status open high confidence

This is an informal meta-conjecture by Joret and Lochet that probabilistic methods such as the Lovász Local Lemma or entropy compression will not suffice on their own to prove the $\Delta+2$ bound for adjacent vertex distinguishing edge colouring. As of 2026, the full $\Delta+2$ conjecture of Zhang, Liu, and Wang remains open, with the best known general upper bound still being $\Delta+19$ established in the source paper itself. No subsequent work has achieved $\Delta+2$ by any method (which would have forced a reassessment of the conjecture's plausibility), and no formal analysis has appeared confirming or refuting the insufficiency claim about probabilistic techniques.

Reviewer notes. This conjecture is informal and not mathematically falsifiable in the usual sense — it would be 'disproved' only if someone produced a proof of the $\Delta+2$ bound using purely probabilistic methods. No such proof exists as of the review date. The status 'open' reflects that the underlying $\Delta+2$ conjecture is unresolved and no follow-up paper has addressed the probabilistic-methods limitation claim directly. The best general bound remains $\Delta+19$ (Joret–Lochet 2020, the source paper). A December 2025 arXiv paper (2512.10827) addresses vertex-distinguishing edge coloring but is a distinct problem.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. One could suspect, as we do, that probabilistic methods such as the Local Lemma or entropy compression will probably not be enough on their own to prove the $\Delta+2$ bound from Conjecture 1, assuming the conjecture is true.

Context

After reducing Hatami's $\Delta+300$ bound to $\Delta+19$ using entropy compression, the authors reflect on the limitations of probabilistic techniques for fully resolving the Zhang–Liu–Wang conjecture, noting that some extra colours seem inevitably wasted in any random process.

Notes. Conjectural belief expressed in prose using 'one could suspect, as we do'; no labelled environment.

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