25
$\begingroup$

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

$\endgroup$
4
  • $\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$ Nov 9, 2013 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$ Nov 9, 2013 at 18:21
  • $\begingroup$ Ah! Neighboring vertices must get different colors. OK, I'll stop commenting for a bit. $\endgroup$ Nov 9, 2013 at 18:24
  • $\begingroup$ Why exactly did you offer a bounty? Wasn't Flo's answer credible enough? $\endgroup$
    – domotorp
    Dec 6, 2016 at 14:55

1 Answer 1

19
+50
$\begingroup$

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.

$\endgroup$
2
  • 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$ Nov 9, 2013 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$ Nov 10, 2013 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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