PDF

Discussiones Mathematicae Graph Theory 33(2) (2013) 289-306
DOI: https://doi.org/10.7151/dmgt.1659

Vertex-distinguishing IE-total colorings of complete bipartite graphs K_m,n(m<n)

Xiang'en Chen, Yuping Gao and Bing Yao College of Mathematics and Information Science Northwest Normal University, Lanzhou 730070, P. R. China

Abstract

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C(u) be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χ_vt^ie(G), and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. VDIET colorings of complete bipartite graphs K_m,n(m < n) are discussed in this paper. Particularly, the VDIET chromatic numbers of K_m,n(1 ≤ m ≤ 7,m < n) as well as complete graphs K_n are obtained.

Keywords: complete bipartite graphs, IE-total coloring, vertex-distinguishing IE-total coloring, vertex-distinguishing IE-total chromatic number

2010 Mathematics Subject Classification: 05C15.

References

[1]	P.N. Balister, B. Bollobás and R.H. Shelp, Vertex distinguishing colorings of graphs with Δ(G)=2, Discrete Math. 252 (2002) 17--29, doi: 10.1016/S0012-365X(01)00287-4.
[2]	P.N. Balister, O.M. Riordan and R.H. Schelp, Vertex distinguishing edge colorings of graphs, J. Graph Theory 42 (2003) 95--109, doi: 10.1002/jgt.10076.
[3]	C. Bazgan, A. Harkat-Benhamdine, H. Li and M. Woźniak, On the vertex-distinguishing proper edge-colorings of graphs, J. Combin. Theory (B) 75 (1999) 288--301, doi: 10.1006/jctb.1998.1884.
[4]	A.C. Burris and R.H. Schelp, Vertex-distinguishing proper edge-colorings, J. Graph Theory 26 (1997) 73--82, doi: 3.0.CO;2-C">10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C.
[5]	J. Černý, M. Horňák and R. Soták, Observability of a graph, Math. Slovaca 46 (1996) 21--31.
[6]	X. Chen, Asymptotic behaviour of the vertex-distinguishing total chromatic numbers of n-cube, J. Northwest Univ. 41(5) (2005) 1--3.
[7]	F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: F. Harary, J.S. Maybee (Eds.), Graphs and Application, New York (1985) 147--162.
[8]	M. Horňák and R. Soták, Observability of complete multipartite graphs with equipotent parts, Ars Combin. 41 (1995) 289--301.
[9]	M. Horňák and R. Soták, Asymptotic behaviour of the observability of Qn, Discrete Math. 176 (1997) 139--148, doi: 10.1016/S0012-365X(96)00292-0.
[10]	M. Horňák and R. Soták, The fifth jump of the point-distinguishing chromatic index of Kn, n, Ars Combin. 42 (1996) 233--242.
[11]	M. Horňák and R. Soták, Localization jumps of the point-distinguishing chromatic index of Kn, n, Discuss. Math. Graph Theory 17 (1997) 243--251, doi: 10.7151/dmgt.1051.
[12]	M. Horňák and N. Zagaglia Salvi, On the point-distinguishing chromatic index of complete bipartite graphs, Ars Combin. 80 (2006) 75--85.
[13]	N. Zagaglia Salvi, On the point-distinguishing chromatic index of Kn, n, Ars Combin. 25B (1988) 93--104.
[14]	N. Zagaglia Salvi, On the value of the point-distinguishing chromatic index of Kn, n, Ars Combin. 29B (1990) 235--244.
[15]	Z. Zhang, P. Qiu, B. Xu, J. Li, X.Chen and B.Yao, Vertex-distinguishing total colorings of graphs, Ars Combin. 87 (2008) 33--45.

Received 11 October 2010
Revised 11 July 2011
Accepted 5 March 2012