Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
vertex coloring; multiset coloring; neighbor-distinguishing coloring
vertex coloring; multiset coloring; neighbor-distinguishing coloring
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.
References:
[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 10.1016/j.jctb.2005.01.001 | MR 2145514 | Zbl 1074.05031
[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 2478212 | Zbl 1177.05035
[3] Burris, A. C.: On graphs with irregular coloring number $2$. Congr. Numerantium 100 (1994), 129-140. MR 1382313 | Zbl 0836.05029
[4] Chartrand, G., Escuadro, H., Okamoto, F., Zhang, P.: Detectable colorings of graphs. Util. Math. 69 (2006), 13-32. MR 2212794
[5] Chartrand, G., Lesniak, L., VanderJagt, D. W., Zhang, P.: Recognizable colorings of graphs. Discuss. Math. Graph Theory 28 (2008), 35-57. DOI 10.7151/dmgt.1390 | MR 2438039 | Zbl 1235.05049
[6] Chartrand, G., Zhang, P.: Introduction to Graph Theory. McGraw-Hill, Boston (2005). Zbl 1096.05001
[7] Escuadro, H., Okamoto, F., Zhang, P.: A three-color problem in graph theory. Bull. Inst. Comb. Appl. 52 (2008), 65-82. MR 2394744 | Zbl 1146.05022
[8] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Comb. Theory Ser. B 91 2004 151-157. DOI 10.1016/j.jctb.2003.12.001 | MR 2047539
[9] Radcliffe, M., Zhang, P.: Irregular colorings of graphs. Bull. Inst. Comb. Appl. 49 (2007), 41-59. MR 2285522 | Zbl 1119.05047
Search
Partner of
