On multiset colorings of generalized corona graphs

Feng, Yun, and Lin, Wensong. "On multiset colorings of generalized corona graphs." Mathematica Bohemica 141.4 (2016): 431-455. <http://eudml.org/doc/287555>.

@article{Feng2016,
abstract = {A vertex $k$-coloring of a graph $G$ is a multiset $k$-coloring if $M(u)\ne 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 multiset chromatic number$\chi _\{m\}(G)$ of $G$. For an integer $\ell \ge 0$, the $\ell $-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 $\ell $-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$.},
author = {Feng, Yun, Lin, Wensong},
journal = {Mathematica Bohemica},
keywords = {multiset coloring; multiset chromatic number; generalized corona of a graph; neighbor-distinguishing coloring},
language = {eng},
number = {4},
pages = {431-455},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On multiset colorings of generalized corona graphs},
url = {http://eudml.org/doc/287555},
volume = {141},
year = {2016},
}

TY - JOUR
AU - Feng, Yun
AU - Lin, Wensong
TI - On multiset colorings of generalized corona graphs
JO - Mathematica Bohemica
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 141
IS - 4
SP - 431
EP - 455
AB - A vertex $k$-coloring of a graph $G$ is a multiset $k$-coloring if $M(u)\ne 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 multiset chromatic number$\chi _{m}(G)$ of $G$. For an integer $\ell \ge 0$, the $\ell $-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 $\ell $-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$.
LA - eng
KW - multiset coloring; multiset chromatic number; generalized corona of a graph; neighbor-distinguishing coloring
UR - http://eudml.org/doc/287555
ER -