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) not equal f (v) for each edge uv 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 chi(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 chi lid(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) chi(lid)(G square H) <= chi(G)chi(H) -1 and (b) chi(lid)(G x H) <= chi(G)chi(H). Here G square H and G x H denote the Cartesian and tensor products of G and H, respectively. We determine the lid-chromatic numbers of Cm square Pn, Cm square Cn, Pm x Pn, Cm x Pn and Cm x Cn, where Cm and Pn denote a cycle and a path on m and n vertices, respectively. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.