The multiset chromatic number of a graph. (English) Zbl 1212.05071

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

Math. Bohem. 134, No. 2, 191-209 (2009).

Summary: 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\geq 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\leq k\leq n\) and \(n\geq 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.

MSC:

05C15

Coloring of graphs and hypergraphs

Keywords:

vertex coloring; multiset coloring; multiset chromatic number; neighbor-distinguishing coloring