The multiset chromatic number of a graph

Chartrand, Gary ; Okamoto, Futaba ; Salehi, Ebrahim ; Zhang, Ping

Mathematica Bohemica, Tome 134 (2009) no. 2, pp. 191-209.

Résumé

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.

Détail

DOI : 10.21136/MB.2009.140654

Classification : 05C15
Keywords: vertex coloring; multiset coloring; neighbor-distinguishing coloring