| Title:
|
On multiset colorings of generalized corona graphs (English) |
| Author:
|
Feng, Yun |
| Author:
|
Lin, Wensong |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
141 |
| Issue:
|
4 |
| Year:
|
2016 |
| Pages:
|
431-455 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
multiset coloring |
| Keyword:
|
multiset chromatic number |
| Keyword:
|
generalized corona of a graph |
| Keyword:
|
neighbor-distinguishing coloring |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 06674854 |
| idMR:
|
MR3576791 |
| DOI:
|
10.21136/MB.2016.0053-14 |
| . |
| Date available:
|
2017-01-03T15:12:48Z |
| Last updated:
|
2020-07-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145959 |
| . |
| Reference:
|
[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. Zbl 1074.05031, MR 2145514, 10.1016/j.jctb.2005.01.001 |
| Reference:
|
[2] Baril, J.-L., Togni, O.: Neighbor-distinguishing $k$-tuple edge-colorings of graphs.Discrete Math. 309 (2009), 5147-5157. Zbl 1179.05041, MR 2548916, 10.1016/j.disc.2009.04.003 |
| Reference:
|
[3] Burris, A. C., Schelp, R. H.: Vertex-distinguishing proper edge-colorings.J. Graph Theory 26 (1997), 73-82. Zbl 0886.05068, MR 1469354, 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C |
| Reference:
|
[4] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs.Discuss. Math., Graph Theory 28 (2008), 35-57. Zbl 1235.05049, MR 2438039, 10.7151/dmgt.1390 |
| Reference:
|
[5] Chartrand, G., Okamoto, F., Salehi, E., Zhang, P.: The multiset chromatic number of a graph.Math. Bohem. 134 (2009), 191-209. Zbl 1212.05071, MR 2535147 |
| Reference:
|
[6] Feng, Y., Lin, W.: A proof of a conjecture on multiset coloring the powers of cycles.Inf. Process. Lett. 112 (2012), 678-682. Zbl 1248.05064, MR 2944394, 10.1016/j.ipl.2012.06.004 |
| Reference:
|
[7] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours.J. Comb. Theory, Ser. B 91 (2004), 151-157. Zbl 1042.05045, MR 2047539, 10.1016/j.jctb.2003.12.001 |
| Reference:
|
[8] Okamoto, F., Salehi, E., Zhang, P.: On multiset colorings of graphs.Discuss. Math., Graph Theory 30 (2010), 137-153. Zbl 1214.05030, MR 2676069, 10.7151/dmgt.1483 |
| Reference:
|
[9] Radcliffe, M., Zhang, P.: Irregular colorings of graphs.Bull. Inst. Comb. Appl. 49 (2007), 41-59. Zbl 1119.05047, MR 2285522 |
| Reference:
|
[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. Zbl 1080.05036, MR 2158269, 10.1360/03YS0207 |
| Reference:
|
[11] Zhang, Z., Liu, L., Wang, J.: Adjacent strong edge coloring of graphs.Appl. Math. Lett. 15 (2002), 623-626. Zbl 1008.05050, MR 1889513, 10.1016/S0893-9659(02)80015-5 |
| Reference:
|
[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. Zbl 1224.05203, MR 2414004 |
| . |
