Geodesic
On multiset colorings of generalized corona graphs
Mathematica Bohemica, Tome 141 (2016) no. 4, pp. 431-455
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/MB.2016.0053-14
Classification : 05C15
Keywords: multiset coloring; multiset chromatic number; generalized corona of a graph; neighbor-distinguishing coloring 
@article{10_21136_MB_2016_0053_14,
     author = {Feng, Yun and Lin, Wensong},
     title = {On multiset colorings of generalized corona graphs},
     journal = {Mathematica Bohemica},
     pages = {431--455},
     year = {2016},
     volume = {141},
     number = {4},
     doi = {10.21136/MB.2016.0053-14},
     mrnumber = {3576791},
     zbl = {06674854},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2016.0053-14/}
}
TY  - JOUR
AU  - Feng, Yun
AU  - Lin, Wensong
TI  - On multiset colorings of generalized corona graphs
JO  - Mathematica Bohemica
PY  - 2016
SP  - 431
EP  - 455
VL  - 141
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2016.0053-14/
DO  - 10.21136/MB.2016.0053-14
LA  - en
ID  - 10_21136_MB_2016_0053_14
ER  - 
%0 Journal Article
%A Feng, Yun
%A Lin, Wensong
%T On multiset colorings of generalized corona graphs
%J Mathematica Bohemica
%D 2016
%P 431-455
%V 141
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2016.0053-14/
%R 10.21136/MB.2016.0053-14
%G en
%F 10_21136_MB_2016_0053_14
Feng, Yun; Lin, Wensong. On multiset colorings of generalized corona graphs. Mathematica Bohemica, Tome 141 (2016) no. 4, pp. 431-455. doi: 10.21136/MB.2016.0053-14

[1] Addario-Berry, L., Aldred, R. E. L., Dalal, K., Reed, B. A.: Vertex colouring edge partitions. J. Comb. Theory, Ser. B 94 (2005), 237-244. | DOI | MR | Zbl

[2] Baril, J.-L., Togni, O.: Neighbor-distinguishing $k$-tuple edge-colorings of graphs. Discrete Math. 309 (2009), 5147-5157. | DOI | MR | Zbl

[3] Burris, A. C., Schelp, R. H.: Vertex-distinguishing proper edge-colorings. J. Graph Theory 26 (1997), 73-82. | DOI | MR | Zbl

[4] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs. Discuss. Math., Graph Theory 28 (2008), 35-57. | DOI | MR | Zbl

[5] Chartrand, G., Okamoto, F., Salehi, E., Zhang, P.: The multiset chromatic number of a graph. Math. Bohem. 134 (2009), 191-209. | MR | Zbl

[6] Feng, Y., Lin, W.: A proof of a conjecture on multiset coloring the powers of cycles. Inf. Process. Lett. 112 (2012), 678-682. | DOI | MR | Zbl

[7] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Comb. Theory, Ser. B 91 (2004), 151-157. | DOI | MR | Zbl

[8] Okamoto, F., Salehi, E., Zhang, P.: On multiset colorings of graphs. Discuss. Math., Graph Theory 30 (2010), 137-153. | DOI | MR | Zbl

[9] Radcliffe, M., Zhang, P.: Irregular colorings of graphs. Bull. Inst. Comb. Appl. 49 (2007), 41-59. | MR | Zbl

[10] Zhang, Z., Chen, X., Li, J., Yao, B., Lu, X., Wang, J.: On adjacent-vertex-distinguishing total coloring of graphs. Sci. China, Ser. A 48 (2005), 289-299. | DOI | MR | Zbl

[11] Zhang, Z., Liu, L., Wang, J.: Adjacent strong edge coloring of graphs. Appl. Math. Lett. 15 (2002), 623-626. | DOI | MR | Zbl

[12] Zhang, Z., Qiu, P., Xu, B., Li, J., Chen, X., Yao, B.: Vertex-distinguishing total coloring of graphs. Ars Comb. 87 (2008), 33-45. | MR | Zbl

Cité par Sources :