Abstract: Call a graph non-trivial if it is connected and has at least 3 vertices. In a recent article (JCTB 2004), Karonski, Luczak, and Thomasson raised the following Question: Is it possible to weight the edges of any non-trivial graph with the integers 1, 2, and 3 such that if we color each vertex v of G by the sum of the weights of the edges incident with v then we obtain a proper coloring of G?
Karonski et al. showed that the answer to the above question is positive for any non-trivial complete graph (i.e, of order at least 3) and for any non-trivial graph with (classical) chromatic number at most 3. In this talk, we will discuss the above question and present some basic results on this ongoing project.