← All problems

The 1–2–3 Conjecture for neighbour-sum-distinguishing edge weightings

7 years old · traced to

Let GG be a connected graph with at least three vertices. An edge weighting assigns a weight from {1,2,3}\{1,2,3\} to every edge of GG, and the sum at a vertex is the sum of the weights on its incident edges. 1–2–3 Conjecture. Every such graph has an edge weighting for which adjacent vertices receive distinct sums of their incident weights. This conjecture asks whether three edge weights always suffice to distinguish the incident-weight sums of adjacent vertices; it remains open in general, although the paper proves the Standard (2,2)(2,2)-Conjecture for graphs with sufficiently large minimum degree.

Equivalent formulations
  1. A graph G=(V,E)G=(V,E) has no isolated edges if none of its connected components is a single edge. A weighting cspanomega:E→{1,2,3}cspanomega:E\to\{1,2,3\} is sum-distinguishing if the weighted degrees

    sω(v):=∑e∈Evω(e)s_\omega(v):=\sum_{e\in E_v}\omega(e)

    are distinct for the endpoints of every edge, where EvE_v is the set of edges incident with vv. 1–2–3 Conjecture. For every graph G=(V,E)G=(V,E) without isolated edges, there exists a weighting ω:E→{1,2,3}\omega:E\to\{1,2,3\} that sum-distinguishes all neighbours in GG. This is a fundamental open problem on graph edge-weightings; the claim is open in general.

    source: Julien Bensmail and Jakub Przybyło, “Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture”, arXiv:1803.07409 (2018).

References
  1. Jakub Przybyło, “On the Standard (2,2)-Conjecture”, arXiv:1911.00867 (2019).

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.