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.
For a nontrivial connected graph $G$, let $c\: V(G)\to \Bbb N$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v$ of $G$, the neighborhood color set ${\rm NC}(v)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if ${\rm NC}(u)\ne {\rm NC}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum number of colors required of such a coloring is called the set chromatic number $\chi _s(G)$. A study is made of the set chromatic number of the join $G + H$ of two graphs $G$ and $H$. Sharp lower and upper bounds are established for $\chi _s(G+H)$ in terms of $\chi _s(G)$, $\chi _s(H)$, and the clique numbers $\omega (G)$ and $\omega (H)$.
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.