Multiplicative vertex-colouring weightings of graphs

摘要

In this paper we conjecture that the edges of any non-trivial graph can be weighted with integers 1, 2, 3 in such a way that for every edge uv the product of weights of the edges adjacent to u is different than the product of weights of the edges adjacent to v. It is proven here for cycles, paths, complete graphs and 3-colourable graphs. It is also shown that the edges of every non-trivial graph can be weighted with integers 1, 2, 3, 4 in such a way that the adjacent vertices have different products of incident edge weights. In a total weighting of a simple graph G we assign the positive integers to edges and to vertices of G. We consider a colouring of G obtained by assigning to each vertex v the product of its weight and the weights of its adjacent edges. The paper conjectures that we can get the proper colouring in this way using the weights 1, 2 for every simple graph. We show that we can do it using the weights 1, 2, 4 on edges and 1, 2 on vertices.