The 1-2-3 Conjecture

Equivalent formulations 2

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

1. The 1-2-3 Conjecture

   Let $G$ be a nice graph, meaning a graph with no connected component isomorphic to $K_2$. A $k$-edge-weighting assigns to each edge a weight from $\{1,\ldots,k\}$, and $\chi^e_\Sigma(G)$ is the smallest $k$ for which the sums of incident edge weights at the endpoints of every edge are distinct. The 1-2-3 Conjecture. For every nice graph $G$,

   $$\chi^e_\Sigma(G)\leq 3.$$

   The conjecture is presented as a well-known conjecture raised by Karoński, Łuczak and Thomason in 2004 and as a motivation for the paper. No resolution status is supplied in the text.

   source: Julien Bensmail, Mohammed Senhaji and Kasper Szabo Lyngsie, “On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture”, arXiv:1704.01172 (2017).

2. The 1-2-3 Conjecture

   Let $G$ be a simple graph. For an edge decoration $f$, define $S(v)=\sum_{x\in N(v)}f(xv)$, and call $f$ cool if $S(u)\ne S(v)$ for every adjacent pair $u,v$. The 1-2-3 Conjecture. Every connected graph with at least two edges has a cool edge decoration from the set $\{1,2,3\}$. The conjecture is known for several classes, and the best general result uses the set $\{1,2,3,4,5\}$; its general validity remains open.

   source: Jarosław Grytczuk, “From the 1-2-3 Conjecture to the Riemann Hypothesis”, arXiv:2003.02887 (2020).