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

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.

Sources & referencesView supporting material

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.