L(2,1)-colorings and Irreducible No-hole Colorings of Cartesian Product of Graphs

An L(2,1)-coloring(or labeling) of a graph G is a mapping f:V(G)→Z+⋃{0} such that |f(u)−f(v)|≥2 for all edges uv of G, and |f(u)−f(v)|≥1 if d(u,v)=2, where d(u,v) is the distance between vertices u and v in G. The span of an L(2,1)-coloring is the maximum color assigned by it. The span of a graph G, denoted by λ(G), is the smallest positive integer λ such that there is an L(2,1) coloring of G using colors from {0,⋯,λ}. A no-hole coloring is defined to be an L(2,1)-coloring of a graph with span k which uses all the colors from {0,1,⋯,k} for some integer k not necessarily the span of the graph. An L(2,1)-coloring is defined as irreducible if color of none of the vertices can be decreased and yield another L(2,1)-coloring of the same graph. An irreducible no-hole coloring of a graph G, in short inh-coloring of G, is an L(2,1)-coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by λinh(G), is the smallest integer k such that there exists an inh-coloring of G with span k. In this paper we work on the L(2,1)-coloring and inh-coloring of the Cartesian product Km□Cn of complete graphs and cycles and find the exact values of λ(Km□Cn) and λinh(Km□Cn) for some values of m and n, and give upper bounds to the same in the remaining cases. We also give two upper bounds of the span of the Cartesian product of two arbitrary graphs which are better than the upper bound of Shao and Yeh [Shao, Z., and R. K. Yeh, The L(2,1)-labeling and operations of graphs, IEEE Trans. Circuits Syst. I Reg. Papers 52 (2005), 668-671] in some cases.