The multiset chromatic number of a graph

Mathematica Bohemica (2009)

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

top

Abstract

top
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}\left(G\right)$ of $G$. For every graph $G$, ${\chi }_{m}\left(G\right)$ is bounded above by its chromatic number $\chi \left(G\right)$. 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}\left({C}_{n}^{k}\right)=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}\left(G\right)=k$. For $k=n-2$, all such graphs $G$ are determined.

How to cite

top

Chartrand, 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
1. 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
2. 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
3. Burris, A. C., On graphs with irregular coloring number $2$, Congr. Numerantium 100 (1994), 129-140. (1994) Zbl0836.05029MR1382313
4. Chartrand, G., Escuadro, H., Okamoto, F., Zhang, P., Detectable colorings of graphs, Util. Math. 69 (2006), 13-32. (2006) MR2212794
5. 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
6. Chartrand, G., Zhang, P., Introduction to Graph Theory, McGraw-Hill, Boston (2005). (2005) Zbl1096.05001
7. Escuadro, H., Okamoto, F., Zhang, P., A three-color problem in graph theory, Bull. Inst. Comb. Appl. 52 (2008), 65-82. (2008) Zbl1146.05022MR2394744
8. 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
9. Radcliffe, M., Zhang, P., Irregular colorings of graphs, Bull. Inst. Comb. Appl. 49 (2007), 41-59. (2007) Zbl1119.05047MR2285522

top

NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.