The multiset chromatic number of a graph
Gary Chartrand, Futaba Okamoto, Ebrahim Salehi, Ping Zhang · Mathematica Bohemica · 2009
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 $\chi _m(G)$ of $G$. For every graph $G$, $\chi _m(G)$ is bounded above by its chromatic number $\chi (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\ge 3$, there exist sufficiently large integers $n$ such that $\chi _m(C_n^k)= 3$. It is determined for which pairs $k, n$ of integers with $1\le k\le n$ and $n\ge 3$, there exists a connected graph $G$ of order $n$ with $\chi _m(G)= k$. For $k= n-2$, all such graphs $G$ are determined.