{
  "id": "2305.17536",
  "version": "v1",
  "published": "2023-05-27T17:35:09.000Z",
  "updated": "2023-05-27T17:35:09.000Z",
  "title": "On Locally Identifying Coloring of Cartesian Product and Tensor Product of Graphs",
  "authors": [
    "Sriram Bhyravarapu",
    "Swati Kumari",
    "I. Vinod Reddy"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "For a positive integer $k$, a proper $k$-coloring of a graph $G$ is a mapping $f: V(G) \\rightarrow \\{1,2, \\ldots, k\\}$ such that $f(u) \\neq f(v)$ for each edge $uv \\in E(G)$. The smallest integer $k$ for which there is a proper $k$-coloring of $G$ is called chromatic number of $G$, denoted by $\\chi(G)$. A \\emph{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 \\emph{locally identifying chromatic number} (for short, \\emph{lid-chromatic number}) of $G$, denoted by $\\chi_{lid}(G)$. In this paper, we study lid-coloring of 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) \\leq \\chi(G) \\chi(H)-1$ and (b) $\\chi_{lid}(G \\times H) \\leq \\chi(G) \\chi(H)$. Here $G \\square H$ and $G \\times H$ denote the Cartesian and tensor products of $G$ and $H$ respectively. We also give exact values of lid-chromatic number of Cartesian product (resp. tensor product) of two paths, a cycle and a path, and two cycles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-05-27T17:35:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "tensor product",
      "cartesian product",
      "locally identifying coloring",
      "smallest integer",
      "closed neighborhoods"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}