The 1-2-3 Conjecture on neighbour sum distinguishing edge colourings

Let GG be a graph with no isolated edges. For an edge colouring c:E(G){1,2,,k}c:E(G)\to\{1,2,\ldots,k\}, define the weighted degree of a vertex vv by

sc(v):=uN(v)c(uv).s_c(v):=\sum_{u\in N(v)}c(uv).

The colouring is neighbour sum distinguishing if sc(u)sc(v)s_c(u)\neq s_c(v) for every adjacent pair u,vu,v.

1-2-3 Conjecture. Every graph GG containing no isolated edges admits a neighbour sum distinguishing 33-edge colouring.

A neighbour sum distinguishing 55-edge colouring is known for every graph without isolated edges, but whether three colours always suffice remains open. The conjecture is equivalent to seeking a locally irregular multigraph obtained by replacing each edge with a number of parallel edges from 11 to 33.

Sources & referencesView supporting material

Primary source

Jakub Przybyło, “On decomposing graphs of large minimum degree into locally irregular subgraphs”, arXiv:1508.01129 (2015).

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.