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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Daniel Soltész
    Commented 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$
    – Flo Pfender
    Commented Nov 10, 2013 at 3:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .