zbMATH — the first resource for mathematics

The multiset chromatic number of a graph. (English) Zbl 1212.05071
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.

05C15 Coloring of graphs and hypergraphs
Full Text: EMIS EuDML