Discussiones Mathematicae Graph Theory 30(1) (2010)
137-153
doi: 10.7151/dmgt.1483
Futaba Okamoto
Mathematics Department |
Ebrahim Salehi
Department of Mathematical Sciences |
Ping Zhang
Department of Mathematics |
On Multiset Colorings of Graphs
From this, it follows that for every positive integer N, there exists
a graph G such that χ_{m}(G)-χ_{m}(
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.
Keywords: vertex coloring, multiset coloring, neighbor-distinguishing coloring.
2010 Mathematics Subject Classification: 05C15.
[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. |
[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. |
[3] | R.L. Brooks, On coloring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. |
[4] | A.C. Burris, On graphs with irregular coloring number 2, Congr. Numer. 100 (1994) 129-140. |
[5] | G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13-32. |
[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. |
[7] | G. Chartrand, F. Okamoto, E. Salehi and P. Zhang, The multiset chromatic number of a graph, Math. Bohem. 134 (2009) 191-209. |
[8] | G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, Boca Raton, FL, 2009). |
[9] | H. Escuadro, F. Okamoto and P. Zhang, A three-color problem in graph theory, Bull. Inst. Combin. Appl. 52 (2008) 65-82. |
[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. |
[11] | M. Radcliffe and P. Zhang, Irregular colorings of graphs, Bull. Inst. Combin. Appl. 49 (2007) 41-59. |
Received 15 November 2008
Revised 28 April 2009
Accepted 28 April 2009