| Title:
|
The multiset chromatic number of a graph (English) |
| Author:
|
Chartrand, Gary |
| Author:
|
Okamoto, Futaba |
| Author:
|
Salehi, Ebrahim |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
134 |
| Issue:
|
2 |
| Year:
|
2009 |
| Pages:
|
191-209 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
vertex coloring |
| Keyword:
|
multiset coloring |
| Keyword:
|
neighbor-distinguishing coloring |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 1212.05071 |
| idMR:
|
MR2535147 |
| DOI:
|
10.21136/MB.2009.140654 |
| . |
| Date available:
|
2010-07-20T17:58:09Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140654 |
| . |
| Reference:
|
[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. Zbl 1074.05031, MR 2145514, 10.1016/j.jctb.2005.01.001 |
| Reference:
|
[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. Zbl 1177.05035, MR 2478212 |
| Reference:
|
[3] Burris, A. C.: On graphs with irregular coloring number $2$.Congr. Numerantium 100 (1994), 129-140. Zbl 0836.05029, MR 1382313 |
| Reference:
|
[4] Chartrand, G., Escuadro, H., Okamoto, F., Zhang, P.: Detectable colorings of graphs.Util. Math. 69 (2006), 13-32. MR 2212794 |
| Reference:
|
[5] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs.Discuss. Math. Graph Theory 28 (2008), 35-57. Zbl 1235.05049, MR 2438039, 10.7151/dmgt.1390 |
| Reference:
|
[6] Chartrand, G., Zhang, P.: Introduction to Graph Theory.McGraw-Hill, Boston (2005). Zbl 1096.05001 |
| Reference:
|
[7] Escuadro, H., Okamoto, F., Zhang, P.: A three-color problem in graph theory.Bull. Inst. Comb. Appl. 52 (2008), 65-82. Zbl 1146.05022, MR 2394744 |
| Reference:
|
[8] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours.J. Comb. Theory Ser. B 91 2004 151-157. MR 2047539, 10.1016/j.jctb.2003.12.001 |
| Reference:
|
[9] Radcliffe, M., Zhang, P.: Irregular colorings of graphs.Bull. Inst. Comb. Appl. 49 (2007), 41-59. Zbl 1119.05047, MR 2285522 |
| . |
