# A Question on 1, 2 ,3 Conjecture

The 1, 2, 3 conjecture is well-known:

If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers of edges incident with it then we obtain a proper vertex coloring.

Question: Is the following weaker statement true?

For any simple graph $G$ there are three natural numbers $p_G, q_G, r_G$ such that if :

(a) We label any edge of $G$ with a number among $p_G, q_G, r_G$.

(b) We label any vertex of $G$ with the sum of numbers of the incident edges.

Then the vertex labels form a proper vertex coloring of the $G$.

Remark: In other words the question is about the truth of the $1, 2, 3$ conjecture when we replace global numbers $1, 2, 3$ with numbers localized to each given $G$.

• Maybe I don't understand what a vertex proper coloring is. If I look at K_2,n where n is large enough I do not see how to get a good vertex coloring using a limited set of colors on the edges. – The Masked Avenger Nov 9 '13 at 16:33
• So if I understand correctly, the problem is challenging only for degree regular graphs? (Otherwise we could color every edge with the color 1.) – The Masked Avenger Nov 9 '13 at 18:21
• Ah! Neighboring vertices must get different colors. OK, I'll stop commenting for a bit. – The Masked Avenger Nov 9 '13 at 18:24
• Why exactly did you offer a bounty? Wasn't Flo's answer credible enough? – domotorp Dec 6 '16 at 14:55

If you choose $p_G$, $q_G$ and $r_G$, such that $p_G>\Delta~q_G>\Delta^2~r_G>0$, (with $\Delta=\Delta(G)$), then your question is equivalent to "neighbor distinguishing colorings by multisets".