On locally identifying coloring of Cartesian product and tensor product of graphs.

For a positive integer k , a proper k -coloring of a graph G is a mapping f : V (G) → { 1 , 2 , ... , k } such that f (u) ≠ f (v) for each edge u v of G. The smallest integer k for which there is a proper k -coloring of G is called the chromatic number of G , denoted by χ (G). A locally identifying coloring (for short, lid-coloring) of a graph G is a proper k -coloring of G such that every pair of adjacent vertices with distinct closed neighborhoods has distinct set of colors in their closed neighborhoods. The smallest integer k such that G has a lid-coloring with k colors is called locally identifying chromatic number (for short, lid-chromatic number) of G , denoted by χ l i d (G). This paper studies the lid-coloring of the Cartesian product and tensor product of two graphs. We prove that if G and H are two connected graphs having at least two vertices, then (a) χ l i d (G □ H) ≤ χ (G) χ (H) − 1 and (b) χ l i d (G × H) ≤ χ (G) χ (H). Here G □ H and G × H denote the Cartesian and tensor products of G and H , respectively. We determine the lid-chromatic numbers of C m □ P n , C m □ C n , P m × P n , C m × P n and C m × C n , where C m and P n denote a cycle and a path on m and n vertices, respectively. [ABSTRACT FROM AUTHOR]