On multiset colorings of generalized corona graphs
| Autor: | Yun Feng, Wensong Lin |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Mathematica Bohemica, Vol 141, Iss 4, Pp 431-455 (2016) |
| Druh dokumentu: | article |
| ISSN: | 0862-7959 2464-7136 |
| DOI: | 10.21136/MB.2016.0053-14 |
| Popis: | 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$, ${\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$. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|