A vertex k-coloring of a graph G is a multiset k-coloring if M(u) ≠ M(v) for every edge uv ∈ E(G), where M(u) and M(v) denote the multisets of colors of the neighbors of u and v, respectively. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χm(G) of G. For an integer l ≥ 0, the l-corona of a graph G, corl (G), is the graph obtained from G by adding, for each vertex v in G, l new neighbors which are end-vertices. In this paper, the multiset chromatic numbers are determined for l-coronas of all complete graphs, the regular complete multipartite graphs and the Cartesian product Kr K2 of Kr and K2. In addition, we show that the minimum l such that χm(corl (G)) = 2 never exceeds χ(G) − 2, where G is a regular graph and χ(G) is the chromatic number of G.
A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χm(G) of G. For every graph G, χm(G) is bounded above by its chromatic number χ(G). The multiset chromatic number is determined for every complete multipartite graph as well as for cycles and their squares, cubes, and fourth powers. It is conjectured that for each k ≥ 3, there exist sufficiently large integers n such that χm(C k n) = 3. It is determined for which pairs k, n of integers with 1 ≤ k ≤ n and n ≥ 3, there exists a connected graph G of order n with χm(G) = k. For k = n − 2, all such graphs G are determined.