On multiset colorings of generalized corona graphs

Feng, Yun ; Lin, Wensong

Mathematica Bohemica, Tome 141 (2016) no. 4, pp. 431-455.

Résumé

A vertex $k$-coloring of a graph $G$ is a \emph {multiset $k$-coloring} if $M(u)\neq M(v)$ for every edge $uv\in E(G)$, where $M(u)$ and $M(v)$ denote the multisets of colors of the neighbors of $u$ and $v$, respectively. The minimum $k$ for which $G$ has a multiset $k$-coloring is the \emph {multiset chromatic number} $\chi _{m}(G)$ of $G$. For an integer $\ell \geq 0$, the $\ell $-\emph {corona} of a graph $G$, ${\rm cor}^{\ell }(G)$, is the graph obtained from $G$ by adding, for each vertex $v$ in $G$, $\ell $ new neighbors which are end-vertices. In this paper, the multiset chromatic numbers are determined for \mbox {$\ell $-\emph {coronas}} of all complete graphs, the regular complete multipartite graphs and the Cartesian product $K_{r}\square K_2$ of $K_r$ and $K_2$. In addition, we show that the minimum $\ell $ such that $\chi _{m}({\rm cor}^{\ell }(G))=2$ never exceeds $\chi (G)-2$, where $G$ is a regular graph and $\chi (G)$ is the chromatic number of $G$.

Détail

DOI : 10.21136/MB.2016.0053-14

Classification : 05C15
Keywords: multiset coloring; multiset chromatic number; generalized corona of a graph; neighbor-distinguishing coloring