Liu–Wang–Zhang's conjecture on the neighbourhood distinguishing index

At least 13 years old · documented by

Let GG be a connected graph, let Δ(G)\Delta(G) be its maximum degree, and let ndi⁡(G)\operatorname{ndi}(G) be the smallest number of colours in a proper edge colouring for which adjacent vertices receive distinct sets of colours on their incident edges.

Liu–Wang–Zhang's conjecture. If G∉{K2,C5}G\notin\{K_2,C_5\}, then

Δ(G)≤ndi⁡(G)≤Δ(G)+2.\Delta(G)\leq \operatorname{ndi}(G)\leq \Delta(G)+2.

The lower bound is immediate, while the upper bound is known for bipartite graphs and graphs with maximum degree at most three, but remains open in general.

References

Primary source

Ben Seamone, “The 1-2-3 Conjecture and related problems: a survey”, arXiv:1211.5122 (2012).

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.