Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
multiset coloring; multiset chromatic number; generalized corona of a graph; neighbor-distinguishing coloring
multiset coloring; multiset chromatic number; generalized corona of a graph; neighbor-distinguishing coloring
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$.
References:
[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 10.1016/j.jctb.2005.01.001 | MR 2145514 | Zbl 1074.05031
[2] Baril, J.-L., Togni, O.: Neighbor-distinguishing $k$-tuple edge-colorings of graphs. Discrete Math. 309 (2009), 5147-5157. DOI 10.1016/j.disc.2009.04.003 | MR 2548916 | Zbl 1179.05041
[3] Burris, A. C., Schelp, R. H.: Vertex-distinguishing proper edge-colorings. J. Graph Theory 26 (1997), 73-82. DOI 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C | MR 1469354 | Zbl 0886.05068
[4] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs. Discuss. Math., Graph Theory 28 (2008), 35-57. DOI 10.7151/dmgt.1390 | MR 2438039 | Zbl 1235.05049
[5] Chartrand, G., Okamoto, F., Salehi, E., Zhang, P.: The multiset chromatic number of a graph. Math. Bohem. 134 (2009), 191-209. MR 2535147 | Zbl 1212.05071
[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 10.1016/j.ipl.2012.06.004 | MR 2944394 | Zbl 1248.05064
[7] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Comb. Theory, Ser. B 91 (2004), 151-157. DOI 10.1016/j.jctb.2003.12.001 | MR 2047539 | Zbl 1042.05045
[8] Okamoto, F., Salehi, E., Zhang, P.: On multiset colorings of graphs. Discuss. Math., Graph Theory 30 (2010), 137-153. DOI 10.7151/dmgt.1483 | MR 2676069 | Zbl 1214.05030
[9] Radcliffe, M., Zhang, P.: Irregular colorings of graphs. Bull. Inst. Comb. Appl. 49 (2007), 41-59. MR 2285522 | Zbl 1119.05047
[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 10.1360/03YS0207 | MR 2158269 | Zbl 1080.05036
[11] Zhang, Z., Liu, L., Wang, J.: Adjacent strong edge coloring of graphs. Appl. Math. Lett. 15 (2002), 623-626. DOI 10.1016/S0893-9659(02)80015-5 | MR 1889513 | Zbl 1008.05050
[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 2414004 | Zbl 1224.05203
Search
Partner of
