Nov DEC MAR » 10 2015 2016 2017 4 captures 10 Dec 16 - 2 Sep 17

Close Help

On multiset colorings of generalized corona graphs

Yun Feng, Wensong Lin

Received August 1, 2014.   First published August 8, 2016.

Abstract: 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\geq0$, the $\ell$-\emph{corona} of a graph $G$, $ 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( cor^{\ell}(G))=2$ never exceeds $\chi(G)-2$, where $G$ is a regular graph and $\chi(G)$ is the chromatic number of $G$.

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

Classification (MSC 2010): 05C15

DOI: 10.21136/MB.2016.0053-14

Full text available as PDF.

References:
  [1] L. Addario-Berry, R. E. L. Aldred, K. Dalal, B. A. Reed: 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] J.-L. Baril, O. Togni: 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] A. C. Burris, R. H. Schelp: 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] G. Chartrand, L. Lesniak, D. W. VanderJagt, P. Zhang: Recognizable colorings of graphs. Discuss. Math., Graph Theory 28 (2008), 35-57. DOI 10.7151/dmgt.1390 | MR 2438039 | Zbl 1235.05049
  [5] G. Chartrand, F. Okamoto, E. Salehi, P. Zhang: The multiset chromatic number of a graph. Math. Bohem. 134 (2009), 191-209. MR 2535147 | Zbl 1212.05071
  [6] Y. Feng, W. Lin: 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] M. Karoński, T. Łuczak, A. Thomason: 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] F. Okamoto, E. Salehi, P. Zhang: On multiset colorings of graphs. Discuss. Math., Graph Theory 30 (2010), 137-153. DOI 10.7151/dmgt.1483 | MR 2676069 | Zbl 1214.05030
  [9] M. Radcliffe, P. Zhang: Irregular colorings of graphs. Bull. Inst. Comb. Appl. 49 (2007), 41-59. MR 2285522 | Zbl 1119.05047
  [10] Z. Zhang, X. Chen, J. Li, B. Yao, X. Lu, J. Wang: 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] Z. Zhang, L. Liu, J. Wang: 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] Z. Zhang, P. Qiu, B. Xu, J. Li, X. Chen, B. Yao: Vertex-distinguishing total coloring of graphs. Ars Comb. 87 (2008), 33-45. MR 2414004 | Zbl 1224.05203