# The multiset chromatic number of a graph

Gary Chartrand; Futaba Okamoto; Ebrahim Salehi; Ping Zhang

Mathematica Bohemica (2009)

- Volume: 134, Issue: 2, page 191-209
- ISSN: 0862-7959

## Access Full Article

top## Abstract

top## How to cite

topChartrand, Gary, et al. "The multiset chromatic number of a graph." Mathematica Bohemica 134.2 (2009): 191-209. <http://eudml.org/doc/38086>.

@article{Chartrand2009,

abstract = {A vertex coloring of a graph $G$ is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum $k$ for which $G$ has a multiset $k$-coloring is the multiset chromatic number $\chi _m(G)$ of $G$. For every graph $G$, $\chi _m(G)$ is bounded above by its chromatic number $\chi (G)$. The multiset chromatic number is determined for every complete multipartite graph as well as for cycles and their squares, cubes, and fourth powers. It is conjectured that for each $k\ge 3$, there exist sufficiently large integers $n$ such that $\chi _m(C_n^k)= 3$. It is determined for which pairs $k, n$ of integers with $1\le k\le n$ and $n\ge 3$, there exists a connected graph $G$ of order $n$ with $\chi _m(G)= k$. For $k= n-2$, all such graphs $G$ are determined.},

author = {Chartrand, Gary, Okamoto, Futaba, Salehi, Ebrahim, Zhang, Ping},

journal = {Mathematica Bohemica},

keywords = {vertex coloring; multiset coloring; neighbor-distinguishing coloring; vertex coloring; multiset coloring; multiset chromatic number; neighbor-distinguishing coloring},

language = {eng},

number = {2},

pages = {191-209},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {The multiset chromatic number of a graph},

url = {http://eudml.org/doc/38086},

volume = {134},

year = {2009},

}

TY - JOUR

AU - Chartrand, Gary

AU - Okamoto, Futaba

AU - Salehi, Ebrahim

AU - Zhang, Ping

TI - The multiset chromatic number of a graph

JO - Mathematica Bohemica

PY - 2009

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 134

IS - 2

SP - 191

EP - 209

AB - A vertex coloring of a graph $G$ is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum $k$ for which $G$ has a multiset $k$-coloring is the multiset chromatic number $\chi _m(G)$ of $G$. For every graph $G$, $\chi _m(G)$ is bounded above by its chromatic number $\chi (G)$. The multiset chromatic number is determined for every complete multipartite graph as well as for cycles and their squares, cubes, and fourth powers. It is conjectured that for each $k\ge 3$, there exist sufficiently large integers $n$ such that $\chi _m(C_n^k)= 3$. It is determined for which pairs $k, n$ of integers with $1\le k\le n$ and $n\ge 3$, there exists a connected graph $G$ of order $n$ with $\chi _m(G)= k$. For $k= n-2$, all such graphs $G$ are determined.

LA - eng

KW - vertex coloring; multiset coloring; neighbor-distinguishing coloring; vertex coloring; multiset coloring; multiset chromatic number; neighbor-distinguishing coloring

UR - http://eudml.org/doc/38086

ER -

## References

top- Addario-Berry, L., Aldred, R. E. L., Dalal, K., Reed, B. A., 10.1016/j.jctb.2005.01.001, J. Comb. Theory Ser. B 94 (2005), 237-244. (2005) Zbl1074.05031MR2145514DOI10.1016/j.jctb.2005.01.001
- Anderson, M., Barrientos, C., Brigham, R. C., Carrington, J. R., Kronman, M., Vitray, R. P., Yellen, J., Irregular colorings of some graph classes, (to appear) in Bull. Inst. Comb. Appl. Zbl1177.05035MR2478212
- Burris, A. C., On graphs with irregular coloring number $2$, Congr. Numerantium 100 (1994), 129-140. (1994) Zbl0836.05029MR1382313
- Chartrand, G., Escuadro, H., Okamoto, F., Zhang, P., Detectable colorings of graphs, Util. Math. 69 (2006), 13-32. (2006) MR2212794
- Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P., 10.7151/dmgt.1390, Discuss. Math. Graph Theory 28 (2008), 35-57. (2008) Zbl1235.05049MR2438039DOI10.7151/dmgt.1390
- Chartrand, G., Zhang, P., Introduction to Graph Theory, McGraw-Hill, Boston (2005). (2005) Zbl1096.05001
- Escuadro, H., Okamoto, F., Zhang, P., A three-color problem in graph theory, Bull. Inst. Comb. Appl. 52 (2008), 65-82. (2008) Zbl1146.05022MR2394744
- Karoński, M., Łuczak, T., Thomason, A., 10.1016/j.jctb.2003.12.001, J. Comb. Theory Ser. B 91 2004 151-157. MR2047539DOI10.1016/j.jctb.2003.12.001
- Radcliffe, M., Zhang, P., Irregular colorings of graphs, Bull. Inst. Comb. Appl. 49 (2007), 41-59. (2007) Zbl1119.05047MR2285522

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.