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

  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Nov 9 '13 at 16:33
  • $\begingroup$ So if I understand correctly, the problem is challenging only for degree regular graphs? (Otherwise we could color every edge with the color 1.) $\endgroup$ – The Masked Avenger Nov 9 '13 at 18:21
  • $\begingroup$ Ah! Neighboring vertices must get different colors. OK, I'll stop commenting for a bit. $\endgroup$ – The Masked Avenger Nov 9 '13 at 18:24
  • $\begingroup$ Why exactly did you offer a bounty? Wasn't Flo's answer credible enough? $\endgroup$ – 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".

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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Daniel Soltész Nov 9 '13 at 19:54
  • 1
    $\begingroup$ 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 $\endgroup$ – Flo Pfender Nov 10 '13 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.