Geodesic
The multiset chromatic number of a graph
Mathematica Bohemica, Tome 134 (2009) no. 2, pp. 191-209
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/MB.2009.140654
Classification : 05C15
Keywords: vertex coloring; multiset coloring; neighbor-distinguishing coloring 
@article{10_21136_MB_2009_140654,
     author = {Chartrand, Gary and Okamoto, Futaba and Salehi, Ebrahim and Zhang, Ping},
     title = {The multiset chromatic number of a graph},
     journal = {Mathematica Bohemica},
     pages = {191--209},
     year = {2009},
     volume = {134},
     number = {2},
     doi = {10.21136/MB.2009.140654},
     mrnumber = {2535147},
     zbl = {1212.05071},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140654/}
}
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
SP  - 191
EP  - 209
VL  - 134
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140654/
DO  - 10.21136/MB.2009.140654
LA  - en
ID  - 10_21136_MB_2009_140654
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Okamoto, Futaba
%A Salehi, Ebrahim
%A Zhang, Ping
%T The multiset chromatic number of a graph
%J Mathematica Bohemica
%D 2009
%P 191-209
%V 134
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2009.140654/
%R 10.21136/MB.2009.140654
%G en
%F 10_21136_MB_2009_140654
Chartrand, Gary; Okamoto, Futaba; Salehi, Ebrahim; Zhang, Ping. The multiset chromatic number of a graph. Mathematica Bohemica, Tome 134 (2009) no. 2, pp. 191-209. doi: 10.21136/MB.2009.140654

[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 | MR | Zbl

[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. | MR | Zbl

[3] Burris, A. C.: On graphs with irregular coloring number $2$. Congr. Numerantium 100 (1994), 129-140. | MR | Zbl

[4] Chartrand, G., Escuadro, H., Okamoto, F., Zhang, P.: Detectable colorings of graphs. Util. Math. 69 (2006), 13-32. | MR

[5] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs. Discuss. Math. Graph Theory 28 (2008), 35-57. | DOI | MR | Zbl

[6] Chartrand, G., Zhang, P.: Introduction to Graph Theory. McGraw-Hill, Boston (2005). | Zbl

[7] Escuadro, H., Okamoto, F., Zhang, P.: A three-color problem in graph theory. Bull. Inst. Comb. Appl. 52 (2008), 65-82. | MR | Zbl

[8] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Comb. Theory Ser. B 91 2004 151-157. | DOI | MR

[9] Radcliffe, M., Zhang, P.: Irregular colorings of graphs. Bull. Inst. Comb. Appl. 49 (2007), 41-59. | MR | Zbl

Cité par Sources :