zbMATH — the first resource for mathematics

On a $$1,2$$ conjecture. (English) Zbl 1250.05093
Summary: Let us assign positive integers to the edges and vertices of a simple graph $$G$$. As a result we obtain a vertex-colouring of $$G$$ with integers, where a vertex colour is simply a sum of the weight assigned to the vertex itself and the weights of its incident edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary $$G$$? We give a positive answer when $$G$$ is a 3-colourable, complete or 4-regular graph. We also show that it is enough to use weights from 1 to 11, as well as from 1 to $$\lfloor \chi (G) / 2\rfloor +1$$, for an arbitrary graph $$G$$.

MSC:
 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C15 Coloring of graphs and hypergraphs
Full Text: