Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 vertex proper 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 number of vertexes forms a proper vertex coloring of the $G$.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
1  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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