Vertex-coloring edge-weighting of complete r-partite graphs

Abstract

A k-edge-weighting of graph G is a mapping w : E(G) → {1, 2, ···, k}. It is called a vertex-coloring k-edge-weighting if the weighted degrees d_w(v) = Σ_uεN(v) w(uv) of the vertices yield a proper vertex coloring of graph G. Let μ(G) be the minimum k for which G has a vertex-coloring k-edge-weighting. In this note we prove that μ(K_{n1, n2, ···, nr}) is 1 if n₁, n₂, ···, n_r are pairwise distinct, is 3 if n₁ = n₂ = · · · = n_r = 1, and is 2 otherwise.