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

• Published in: Discrete Applied Mathematics 2024-12, Vol.358, p.429-447
• Main Authors: Bhyravarapu, Sriram, Kumari, Swati, Reddy, I. Vinod
• Format: Article
• Language: English
• Subjects: Cartesian product; Graph coloring; Locally identifying coloring; Tensor product
• ISSN: 0166-218X
• DOI: 10.1016/j.dam.2024.07.046

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 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 χ(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 χ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) χlid(G□H)≤χ(G)χ(H)−1 and (b) χlid(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 Cm□Pn, Cm□Cn, Pm×Pn, Cm×Pn and Cm×Cn, where Cm and Pn denote a cycle and a path on m and n vertices, respectively.