The multiset chromatic number of a graph

Chartrand, Gary, et al. "The multiset chromatic number of a graph." Mathematica Bohemica 134.2 (2009): 191-209. <http://eudml.org/doc/38086>.

@article{Chartrand2009,
abstract = {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.},
author = {Chartrand, Gary, Okamoto, Futaba, Salehi, Ebrahim, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {vertex coloring; multiset coloring; neighbor-distinguishing coloring; vertex coloring; multiset coloring; multiset chromatic number; neighbor-distinguishing coloring},
language = {eng},
number = {2},
pages = {191-209},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The multiset chromatic number of a graph},
url = {http://eudml.org/doc/38086},
volume = {134},
year = {2009},
}

TY - JOUR
AU - Chartrand, Gary
AU - Okamoto, Futaba
AU - Salehi, Ebrahim
AU - Zhang, Ping
TI - The multiset chromatic number of a graph
JO - Mathematica Bohemica
PY - 2009
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 134
IS - 2
SP - 191
EP - 209
AB - 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.
LA - eng
KW - vertex coloring; multiset coloring; neighbor-distinguishing coloring; vertex coloring; multiset coloring; multiset chromatic number; neighbor-distinguishing coloring
UR - http://eudml.org/doc/38086
ER -