# 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

## 1 Answer

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".

As far as I know, the best known bound for this problem is proved here:

L. Addario-Berry, R. E. L. Aldred, K. Dalal, and B. A. Reed. Vertex colouring edge partitions. J. Combin. Theory Ser. B, 94(2):237–244, 2005.

They prove that four different edge labels are sufficient, three should be open.

• I was also thinking along these lines, but didn't know about the name "neighbor distinguishing colorings by multisets" so i didn't find anything. I'm half way through the paper by you, Kalkowski and Karonski (math.ucdenver.edu/~fpfender/papers/22.pdf) where you prove something what may be called the "1,2,3,4,5 conjecture". I'll finish it anyway but since you understand it mutch better i'd like to ask: What do you think does the method used there might be helpful for this question? – Daniel Soltész Nov 9 '13 at 19:54
• The specific method there works only for arithmetic progressions, I doubt it could really do much here. This does not mean that some other tricky greedy method does not work, though. For good references on related problems, there is a survey by Ben Seamone: arxiv.org/abs/1211.5122 – Flo Pfender Nov 10 '13 at 3:44