# On multiset colorings of graphs

Futaba Okamoto; Ebrahim Salehi; Ping Zhang

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 1, page 137-153
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topFutaba Okamoto, Ebrahim Salehi, and Ping Zhang. "On multiset colorings of graphs." Discussiones Mathematicae Graph Theory 30.1 (2010): 137-153. <http://eudml.org/doc/270936>.

@article{FutabaOkamoto2010,

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 χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset chromatic number k. It is also shown that for every positive integer N, there is an r-regular graph G such that χ(G) - χₘ(G) = N. In particular, it is shown that χₘ(Kₙ × K₂) is asymptotically √n. In fact, $χₘ(Kₙ × K₂) = χₘ(cor(K_\{n+1\}))$. The corona cor(G) of a graph G is the graph obtained from G by adding, for each vertex v in G, a new vertex v’ and the edge vv’. It is shown that χₘ(cor(G)) ≤ χₘ(G) for every nontrivial connected graph G. The multiset chromatic numbers of the corona of all complete graphs are determined. On Multiset Colorings of Graphs From this, it follows that for every positive integer N, there exists a graph G such that χₘ(G) - χₘ(cor(G)) ≥ N. The result obtained on the multiset chromatic number of the corona of complete graphs is then extended to the corona of all regular complete multipartite graphs.},

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

journal = {Discussiones Mathematicae Graph Theory},

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

language = {eng},

number = {1},

pages = {137-153},

title = {On multiset colorings of graphs},

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

volume = {30},

year = {2010},

}

TY - JOUR

AU - Futaba Okamoto

AU - Ebrahim Salehi

AU - Ping Zhang

TI - On multiset colorings of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 1

SP - 137

EP - 153

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 χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset chromatic number k. It is also shown that for every positive integer N, there is an r-regular graph G such that χ(G) - χₘ(G) = N. In particular, it is shown that χₘ(Kₙ × K₂) is asymptotically √n. In fact, $χₘ(Kₙ × K₂) = χₘ(cor(K_{n+1}))$. The corona cor(G) of a graph G is the graph obtained from G by adding, for each vertex v in G, a new vertex v’ and the edge vv’. It is shown that χₘ(cor(G)) ≤ χₘ(G) for every nontrivial connected graph G. The multiset chromatic numbers of the corona of all complete graphs are determined. On Multiset Colorings of Graphs From this, it follows that for every positive integer N, there exists a graph G such that χₘ(G) - χₘ(cor(G)) ≥ N. The result obtained on the multiset chromatic number of the corona of complete graphs is then extended to the corona of all regular complete multipartite graphs.

LA - eng

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

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

ER -

## References

top- [1] L. Addario-Berry, R.E.L. Aldred, K. Dalal and B.A. Reed, Vertex colouring edge partitions, J. Combin. Theory (B) 94 (2005) 237-244, doi: 10.1016/j.jctb.2005.01.001. Zbl1074.05031
- [2] M. Anderson, C. Barrientos, R.C. Brigham, J.R. Carrington, M. Kronman, R.P. Vitray and J. Yellen, Irregular colorings of some graph classes, Bull. Inst. Combin. Appl., to appear. Zbl1177.05035
- [3] R.L. Brooks, On coloring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
- [4] A.C. Burris, On graphs with irregular coloring number 2, Congr. Numer. 100 (1994) 129-140. Zbl0836.05029
- [5] G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13-32. Zbl1102.05020
- [6] G. Chartrand, L. Lesniak, D.W. VanderJagt and P. Zhang, Recognizable colorings of graphs, Discuss. Math. Graph Theory 28 (2008) 35-57, doi: 10.7151/dmgt.1390. Zbl1235.05049
- [7] G. Chartrand, F. Okamoto, E. Salehi and P. Zhang, The multiset chromatic number of a graph, Math. Bohem. 134 (2009) 191-209. Zbl1212.05071
- [8] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, Boca Raton, FL, 2009). Zbl1169.05001
- [9] H. Escuadro, F. Okamoto and P. Zhang, A three-color problem in graph theory, Bull. Inst. Combin. Appl. 52 (2008) 65-82. Zbl1146.05022
- [10] M. Karoński, T. Łuczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory (B) 91 (2004) 151-157, doi: 10.1016/j.jctb.2003.12.001. Zbl1042.05045
- [11] M. Radcliffe and P. Zhang, Irregular colorings of graphs, Bull. Inst. Combin. Appl. 49 (2007) 41-59. Zbl1119.05047

## 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.