On Locally Identifying Coloring of Graphs

Abstract

A proper coloring of a graph G is said to be locally identifying coloring (lid-coloring for short), if for every pair of adjacent vertices u and v with distinct closed neighborhood, the sets of colors assigned in the closed neighborhood of u and v are distinct. The minimum number of colors required in any lid-coloring of a graph G is called the lid-chromatic number of G, denoted by $\chi _{lid}(G)$.

In this paper, we give a characterization of graphs whose lid-chromatic number equals the number of vertices. Next, we study lid-coloring on several restricted graph classes. We show that for any block graph G, $\chi _{lid}(G) \le 2 \chi (G)$, where $\chi (G)$ denotes the chromatic number of G. We show that the lid-chromatic number of a biconvex bipartite graph can be computed in polynomial time. Finally, we find the lid-chromatic number of the Cartesian and Lexicographic products of paths and cycles.

1 Introduction

All graphs considered in this paper are finite, undirected and simple (without loops and multiple edges). For a graph $G=(V,E)$, we use V(G) and E(G) to denote the vertex set and edge set of G respectively. The open neighborhood of a vertex v, denoted N(v), is the set of vertices adjacent to v and the set $N[v] = N(v) \cup \{v\}$ denote the closed neighborhood of v. Let $f: V(G) \rightarrow \mathbb {N}$ be a vertex coloring of G. For a subset $X \subseteq V(G)$, $f(X)=\{f(v)~|~ v \in X\}$ denotes the set of colors that appear in X.

A vertex coloring f of a graph G is called locally identifying coloring (lid-coloring for short) if (i) f is a proper coloring of G (no two adjacent vertices have the same color) and (ii) for each pair of adjacent vertices u, v with $N[u] \ne N[v]$, we have $f(N[u]) \ne f(N[v])$. The smallest integer k for which G admits a lid-coloring is called the lid-chromatic number of G, denoted by $\chi _{\text {lid}}(G)$. Note that the lid-chromatic number of a graph G is the maximum of the lid-chromatic numbers of its connected components. Therefore, throughout this paper we restrict ourselves to connected graphs.

Locally identifying coloring was introduced by Esperet et al. [2]. They showed that the decision version of the lid-coloring is $\textsc {NP}$-complete on bipartite graphs but polynomial time solvable on trees. They also proved that $\chi _{lid}(G) \le 2 \chi (G)$ for interval graphs, split graphs and cographs and conjectured the same bound for chordal graphs. They also showed that for an outerplanar graph G, $\chi _{lid}(G)\le 20$. Foucaud et al. [4] showed that any graph G with maximum degree $\varDelta$ has a locally identifying coloring with at most $2 \varDelta ^2-3 \varDelta +3$ colors, by answering positively a question raised in the paper [2]. Goncalves [6] showed that for any planar graph G, $\chi _{lid}(G) \le 1280$. They also proved that for any graph class of bounded expansion, the lid-chromatic number is bounded. Martins and Sampaio [7] obtained a linear time algorithms to calculate the lid-chromatic number for some classes of graphs having few $P_4$’s.

Our Contributions: It is easy to see that $\chi (G)=n$ if and only if $G=K_n$. In Sect. 3, we investigate the graphs for which the lid-chromatic number equals n and give a complete characterization of graphs having lid-chromatic number n.

Esperet et al. [2] conjectured that, for any chordal graph G, $\chi _{lid}(G) \le 2 \chi (G)$. They verified the conjecture for subclasses of chordal graphs such as interval graphs, split graphs and cographs. In Sect. 4, we show that the conjecture holds for block graphs, which are a subclass of chordal graphs.

Esperet et al. [2] showed that, if G is bipartite then $\chi _{lid}(G) \le 4$. They also proved that deciding whether a bipartite graph G has $\chi _{lid}(G)\in \{3, 4\}$ is NP-complete. As lid-coloring is NP-complete on bipartite graphs, we focus on biconvex bipartite graphs, which is a subclass of bipartite graphs. In Sect. 5, we show that lid-chromatic number of biconvex bipartite graphs can be computed in polynomial time.

Finally, we investigate lid-coloring on Cartesian product and Lexicographic product of graphs. Proper coloring of various graph products has been well studied  [3, 5, 8, 9]. For example, the chromatic number of the Cartesian product of two graphs G and H [8] is equal to $\max \{\chi (G), \chi (H)\}$. The chromatic number of a lexicographic product of two graphs G and H is equal to the b-fold chromatic number [5] of G, where $b=\chi (G)$. In Sects. 6 and 7, we give exact values of the lid-chromatic number of Cartesian and Lexicographic products of paths and cycles.

2 Preliminaries

We denote the set $\{1, 2, \dots , k\}$ with [k]. Let $c:V(G)\rightarrow [k]$ be a coloring of the vertices of G using k colors. Let $S\subseteq V(G)$, then $c(S)=\{c(v)\mid v\in S\}$. We say an edge $uv\in E(G)$ respects lid-coloring if either (i) $N[u]=N[v]$, or (ii) $c(N[u])\ne c(N[v])$. We associate a distinguishing color for each edge satisfying the condition (ii) in the above sentence. We define a distinguishing color for the edge uv to be a color from $\left( c(N[u])\setminus c(N[v]) \right) \cup \left( c(N[v])\setminus c(N[u])\right)$. That is, a color that is seen in the closed neighborhood of u and not in the closed neighborhood of v or vice-versa. The minimum degree of the graph G is denoted by $\delta (G)$. For more details on graph theoretic notation or terminology, we refer the reader to the textbook [1]. The lid-chromatic numbers of paths and cycles are stated below.

Due to space constraints, the proofs of the results marked $(\star )$ are presented in the full version of the paper.

Lemma 1

([4]). For a positive integer n, where $n \ge 2$, we have

$$ \chi _{lid}(P_n) = {\left\{ \begin{array}{ll} 2 &{}\text {if }n =2; \\ 3 &{}\text {if }n\text { is odd }\; \\ 4 &{}\text {if }n\text { is even and }n \ne 2; \\ \end{array}\right. } $$

Lemma 2

([4]). For a positive integer n, where $n \ge 4$, we have

$$ \chi _{lid}(C_n) = {\left\{ \begin{array}{ll} 3 &{}\text {if }n \equiv 0~mod~ 4; \\ 5 &{}\text {if }n=5\text { or }7; \\ 4 &{}\text {otherwise;} \\ \end{array}\right. } $$

3 Graphs with $\chi _{lid}(G) = |V(G)|$

Let $G=(V,E)$ be a graph on n vertices. It is known that $\chi (G)=n$ if and only if $G=K_n$. In this section, we investigate graphs for which the lid-chromatic number equals n. We first show the characteristics of graphs G whose lid-chromatic number is at most $n-1$. Using this, we conclude with the structure of graphs that require n colors.

Theorem 1

Let $G=(V,E)$ be a graph on n vertices. Then $\chi _{lid}(G) \le n-1$ if and only if there exist two non-adjacent vertices $x,y \in V(G)$ such that for every edge $uv \in E(G)$ at least one of the following conditions is satisfied.

• (1) if either u or v belong to $\{x,y\}$

  • (a) $N[u] = N[v]$, or

  • (b) $N[u] \setminus \{x,y\} \ne N[v] \setminus \{x,y\}$.

• (2) Both u and v does not belong to $\{x,y\}$.

  • (a) $N[u] = N[v]$, or

  • (b) $N[u] \setminus \{x,y\} \ne N[v] \setminus \{x,y\}$, or

  • (c) $N[u] \setminus \{x,y\} = N[v] \setminus \{x,y\}$ and

    • (i) if $N(u) \cap \{x,y\} \ne \emptyset$, then $N(v) \cap \{x,y\} = \emptyset$, or

    • (ii) if $N(u) \cap \{x,y\} = \emptyset$, then $N(v) \cap \{x,y\} \ne \emptyset$.

Proof

($\Longrightarrow$) There exists a lid-coloring of G using at most $n-1$ colors. We need to show that there exist two non-adjacent vertices $x,y \in V(G)$ such that for every edge $uv \in E(G)$ at least one of the given two conditions is satisfied. Without loss of generality, let $\chi _{\text {lid}}(G) = n-1$. Otherwise, if $\chi _{lid}(G) < n-1$, we can always replace the repeated colors in the lid-coloring of G with new colors to get a lid-coloring of G that uses $n-1$ colors. Let $c : V(G) \rightarrow [n-1]$ be a lid-coloring of G. There exists two non-adjacent vertices x and y in G such that $c(x)=c(y)$.

Consider an arbitrary edge uv of G.

Case 1: Either u or v belong to $\{x,y\}$.

Without loss of generality, let $u=x$. Suppose the edge xv does not satisfy the conditions 1(a) and 1(b). That is, we have

$$\begin{aligned} N[x] \ne N[v], \text{ and } \end{aligned}$$

(1)

$$\begin{aligned} N[x] \setminus \{x,y\} = N[v] \setminus \{x,y\}. \end{aligned}$$

(2)

From Eqs. (1), (2) and the fact that $c(x)=c(y)$, it is clear that $c(N[x])=c(N[v])$, which is a contradiction to the fact that c is a lid-coloring of G.

Case 2: Both u and v does not belong to $\{x,y\}$.

Suppose that the edge uv does not satisfy any of the three conditions 2(a), 2(b) and 2(c), we have

$$\begin{aligned} N[u] \ne N[v], \end{aligned}$$

(3)

$$\begin{aligned} N[u] \setminus \{x,y\} = N[v] \setminus \{x,y\}, \text{ and } \end{aligned}$$

(4)

$$\begin{aligned} N(u) \cap \{x,y\} \ne \emptyset , N(v) \cap \{x,y\} \ne \emptyset . \end{aligned}$$

(5)

If $N(u) \cap \{x,y\} = N(v) \cap \{x,y\}$, then using (4) we get $N[u] = N[v]$, which is a contradiction to (3). Therefore, using (3),(4) and (5), we get that

$$\begin{aligned} N(u) \cap \{x,y\} \ne N(v) \cap \{x,y\}. \end{aligned}$$

(6)

Using Eq. (4), we have $c(N[u] \setminus \{x,y\} )=c( N[v] \setminus \{x,y\})$. From Eq. (5), we know that u and v have some neighbor in $\{x,y\}$. Since, $c(x)=c(y)$ the set of colors assigned to vertices in N[u] and N[v] are the same in G even though $N[u] \ne N[v]$. This is a contradiction to the assumption that c is a lid-coloring of G.

($\Longleftarrow$) Let G be a graph with two non-adjacent vertices x and y such that for every edge $uv \in E(G)$, at least one of the given conditions is satisfied. We need to show that $\chi _{\text {lid}}(G) \le n-1$.

Let $f : V(G) \rightarrow [n-1]$ be a coloring of G constructed as follows. Assign $f(x)=f(y)=1$. Each of the vertices in $V(G) \setminus \{x,y\}$ are assigned distinct colors from $[n-1] \setminus \{1\}$. We now argue that f is a lid-coloring of G.

Since every vertex in $V(G)\setminus \{x,y\}$ is assigned a distinct color and $xy\notin E(G)$, we have that f is a proper coloring. Consider an arbitrary edge $uv \in E(G)$.

Case 1: Either u or v belongs to $\{x,y\}$.

Without loss of generality we assume that $u=x$. If $N[x]=N[v]$ then there is nothing to prove.

If $N[x] \setminus \{x,y\} \ne N[v] \setminus \{x,y\}$, then as no two vertices in $V(G) \setminus \{x,y\}$ are colored with the same color by f. Therefore $f(N[x]) \ne f(N[v])$.

Case 2: Both u and v does not belong to $\{x,y\}$.

We assume that the edge uv does not satisfy condition 2(a), otherwise there is nothing to prove.

If $N[u] \setminus \{x,y\} \ne N[v] \setminus \{x,y\}$, then as no two vertices in $V(G) \setminus \{x,y\}$ are colored with the same color by f. Therefore, $f(N[u]) \ne f(N[v])$.

Lastly, for any edge $uv \in E(G)$, if $N[u] \setminus \{x,y\} = N[v] \setminus \{x,y\}$, then set of colors (say S) used in $N[u] \setminus \{x,y\}$ is same as the set of colors used in $N[v] \setminus \{x,y\}$. If $N(u) \cap \{x,y\} = \emptyset$, then set of colors in N[u] is S. Since $N(v) \cap \{x,y\} \ne \emptyset$, set of colors used in N[v] is $S \cup \{1\}$. Therefore, set of colors used in N[u] is not same as set of colors used in N[v]. Similarly, if $N(u) \cap \{x,y\} \ne \emptyset$, then set of colors in N[u] is $S \cup \{1\}$. Since, $N(v) \cap \{x,y\} = \emptyset$, set of colors in N[v] is S. Therefore, set of colors used in N[u] is not same as set of colors used in N[v].

Hence, f is a lid-coloring that uses $n-1$ colors.    $\square$

Given a graph G, if G does not satisfy the conditions mentioned in Theorem 1, then the lid-chromatic number of G is equal to $|V(G)|=n$.

Thus, as a consequence of Theorem 1, we have the following corollary.

Corollary 1

Given a graph G, we can decide in polynomial time if $\chi _{lid}(G)=n$, where n is the number of vertices of the graph G.

4 Block Graphs

This section is devoted to block graphs. We prove that every block graph has lid-chromatic number at most $2\omega (G)$, where $\omega (G)$ is the size of a largest clique in G.

Definition 1

(Block Graphs [1]). A vertex u of a connected graph G is called a cut vertex if $G-u$ is disconnected. A block of a graph G is a maximal connected induced subgraph of G that has no cut vertex. A block graph is a graph in which every block is a clique.

To prove the result, we use the notion of block decomposition of graphs. Let $G=(V,E)$ be a block graph with q blocks $B_1, \ldots , B_q$. The block decomposition of G is a tree denoted by $T_B=(V_B, E_B)$ where $V_B=\{B_1, \ldots , B_q\}$ and $E_B=\{B_iB_j~|~B_i \cap B_j \ne \emptyset \}$. We root the tree $T_B$ at a node $B_R$ having at least two cut vertices. For example, the block decomposition of $P_4$ (the path on four vertices) contains three blocks $\{B_1, B_2, B_3\}$ where every block is a $K_2$ with $B_2$ being adjacent to both $B_1$ and $B_3$. The level of a block B denoted by $\ell (B)$ is the distance of B from the root block $B_R$ in $T_B$. Clearly $\ell (B_R)=0$. We also define level of a vertex v as $\ell (v)=\min \{\ell (B)\mid v\in V(B)\}$. For each block B at level $p\ge 1$, we call the vertex $v\in B$ as the distinguishing ancestor vertex of B, denoted by dav(B), if and only if $\ell (v) <\ell (B)$. We call $B'$ as the parent block of B if $B'$ is the parent of B in $T_B$.

For a vertex $v \in V(G)$, let

$$D_1(v)=\{B\mid \ell (B)=\ell (v)+1 \text{ and } dav(B)=v\}\text{, } \text{ and } $$

$$D_2(v)=\{B\mid \ell (B)=\ell (v)+2 , \text{ and } dist_G(dav(B), v)=1 \}, $$

where $dist_G(w, w')$ is the length of a shortest path from w to $w'$ in G.

Notice that if v is not a cut-vertex in G, then $D_1(v)=D_2(v)=\emptyset$. An illustration of a block decomposition is shown in Fig. 1.

We first present the overall idea of the algorithm. We consider the blocks level by level (starting with level 0) and in each level we process the blocks from left to the right in some arbitrary order. First, all the vertices in the root block are assigned colors. When a non-root block B is considered for coloring as in the above ordering, all vertices at level at most $\ell (B)-1$ are assigned colors.

We color each block B in two phases. In its first phase, exactly two vertices of B are colored while coloring its parent block. After the first phase, we find a set of forbidden colors for B. In its second phase, we arbitrarily assign colors to the remaining uncolored vertices of B from the set [2k] excluding its forbidden colors.

Theorem 2

If G is a block graph, then $\chi _{lid}(G)\le 2\omega (G)$.

Proof

Given a block graph G and its block decomposition, we show that $\chi _{lid}(G)\le 2k$, where $k=\omega (G)$. To prove the result, we present a lid-coloring $c:V(G)\rightarrow [2k]$ of G using at most 2k colors.

Fig. 1.

An illustration of a block decomposition of G where each $B_i$ represents a block. Considering $\ell (B_1)=p$, we have $\ell (B_2)=\ell (B_3)=\ell (B_4)=\ell (B_5)=p+1$, $\ell (B_6)=p+2$ and $\ell (B_7)=\ell (B_8)=p+3$. Also $dav(B_1)=x$, $dav(B_2)=dav(B_3)=v$, and $dav(B_6)=a$. For the vertex x, we have $D_1(x)=\{B_1\}$ and $D_2(x)=\{B_2, B_3, B_4, B_5\}$. For the vertex a, we have $D_1(a)=\{B_6\}$ and for the vertex b, we have $D_1(b)=\{B_7\}$.

Coloring Procedure: Let N(B) be the set of colors that are forbidden to be used in the block B. Initially $N(B)=\emptyset$, for each block B. We consider the blocks level by level and from left to right in each level.

At each block B, for each cut vertex $v\in V(B)\setminus \{dav (B)\}$, we identify two colors W(v) and A(v). For each edge vw, where $w\in V(B)\setminus \{dav (B)\}$, the color W(v) serves as a distinguishing color for the edge vw. Similarly, A(v) serves as a distinguishing color for the edges vw where $w\notin V(B)$. The intuition is that the edge vw respects lid-coloring because of the colors W(v) and A(v) depending on whether or not $w\in V(B)$.

Coloring the Root Block $B_R$: Let $\{v_1, v_2, \dots , v_{k'}\}$, where $k'\le k$, be the vertices of $B_R$. Each vertex in $V(B_R)$ is assigned a distinct color from $\{1, 2, \dots , 2k\}$. WLOG, let two vertices $v_1, v_2$ from $B_R$ be assigned the colors $c_1$ and $c_2$ respectively. For each cut vertex v of $B_R$, we do the following:

• 1.

  • (a) If $v\ne v_1$ set $A(v)=c_1$, else set $A(v)=c_2$.

  • (b) Forbid the color A(v) to be used in all the blocks from $D_1(v)\cup D_2(v)$. That is, for all $B\in D_1(v)\cup D_2(v)$, update $N(B)=N(B)\cup \{A(v)\}$.

• 2. Choose W(v) to be a color from $[2k]\setminus (c(B_R)\cup N(B'))$ such that for any two cut vertices $u, u'$ of $B_R$, $W(u)\ne W(u')$, where $B'$ is some block in $D_1(v)$. Here $c(B_R)$ represents the colors assigned to the vertices in $V(B_R)$, i.e., $c(B_R)=\{c(w)\mid w\in V(B_R)\}$, and $N(B')$ is the set of colors forbidden to be used in $V(B')$.

  Let $S(B_R)$ be the set of associated colors for the cut vertices of $B_R$. That is, $S(B_R)=\{W(v)\mid v \text{ is } \text{ a } \text{ cut } \text{ vertex } \text{ of } B_R\}$. We now color a vertex in each block of $D_1(v)$ in the following manner. For each $B' \in D_1(v)$, choose an arbitrary uncolored vertex $v'\in V(B')$ and assign $c(v')=W(v)$. Then update $N(B')=N(B')\cup (S(B_R)\setminus \{c(v')\})$.

Notice that after processing all the cut vertices of $B_R$, exactly two vertices in each of the blocks at level 1 are colored.

Coloring a Non-Root Block B: In the first phase coloring of B, exactly two vertices of B are colored. Let the two colored vertices be dav(B) and $v'$. In the second phase coloring of B, we arbitrarily assign colors to the uncolored vertices in V(B) from $[2k]\setminus \left( N(B) \cup \{c(dav(B)), c(v')\}\right)$.

For each cut vertex $v\in V(B)\setminus \{dav(B)\}$, we do the following:

• 1.

  • (a) Set $A(v)=c(dav(B))$.

  • (b) Forbid the color A(v) to be used in all blocks from $D_1(v)\cup D_2(v)$. That is, for all $B\in D_1(v)\cup D_2(v)$, update $N(B)=N(B)\cup \{A(v)\}$.

• 2. This step is similar to the Step 2 of the root block case where each instance of $B_R$ is to be replaced by B. Also whenever we talk about the cut vertices of $B_R$, we replace it with the the cut vertices in $V(B)\setminus \{dav(B)\}$.

We recursively apply the above coloring procedure on the blocks in order and complete the coloring. We now show that the coloring obtained is a lid-coloring of G. Before we prove the correctness, we will look at the following claim.

Claim

For any non-root block B, we have $|N(B)|\le k+2$.

Proof

Recall that, the set N(B) represents the set of colors that are forbidden in B. Let $B'$ and $B''$ be the parent and the grand-parent of B in $T_B$ respectively. From the description of the algorithm, the colors of the vertices dav(B) and $dav(B')$ are forbidden in B. In the worst case, $B'$ contains at most k cut vertices. For each cut vertex $v\in V(B')$, we assigned a color W(v) which is forbidden to be used in $B'$. Therefore by combining all, at most $k+2$ colors are forbidden in B.

Correctness: We first need to show why it is possible to color the uncolored vertices of each block B in its second phase of coloring. From the above claim, we have that $|N(B)|\le k+2$. Since B has exactly two colored vertices after its first phase of coloring, the number of uncolored vertices in B is at most $k-2$. We have the budget to color the remaining with $[2k]\setminus N(B)$.

It is easy to see that the coloring yields a proper coloring. We now show that each edge respects lid-coloring. Let uv be an edge. We have the following cases.

• $\ell (u)=\ell (v)$ Let $u,v\in V(B)$. If none of them are cut vertices of B, then $N[u]=N[v]$. If exactly one of them is a cut vertex, say u. Then by the coloring procedure, there exists a color $W(u)\in c(N[u])$ and $W(u)\notin c(N[v])$. Else both u and v are cut vertices. Then $W(u)\in c(N[u])$ and $W(u)\notin c(N[v])$. Also $W(v)\notin c(N[u])$ and $W(v)\in c(N[v])$.

• $\ell (u)\ne \ell (v)$

  Let $u,v\in V(B)$ for some block B. Then it follows that exactly one of v or u is dav(B). WLOG let $dav(B)=u$ and $B^{\star }$ be the parent block of B where $u\in V(B^{\star })$. While coloring the block $B^{\star }$, we had chosen the color of a vertex in $B^{\star }$ to be the A(u) and forbid the color A(u) in $D_1(u)\cup D_2(u)$. This forces none of the neighbors of v in $D_1(v)$ to be assigned the color A(u). Hence the edge uv respects lid-coloring.

The edge uv respects lid-coloring in all the above cases. This completes the proof of Theorem 2.    $\square$

Remark: Consider the graph $P_4$. From Lemma 1, we have that $\chi _{lid}(P_4)=4$. It is easy to see that $P_4$ is a block graph and the bound in Theorem 2 is tight.

5 Biconvex Bipartite Graphs

Definition 2

(Biconvex Bipartite Graph). A bipartite graph $G = (X \cup Y, E)$ is called convex bipartite graph over the vertex set X if X can be enumerated such that for all $y \in Y$ the vertices adjacent to y are consecutive with respect to the ordering on X. If G is convex over both X and Y, it is said to be biconvex bipartite graph.

Theorem 3

If $G=(X \cup Y,E)$ is a connected biconvex bipartite graph having at least three vertices, then

$$ \chi _{lid}(G)= {\left\{ \begin{array}{ll} 4,&{} \text {if Z }\cap \text { X }\ne \emptyset \text { and Z }\cap \text { Y }\ne \emptyset \\ 3,&{} \text {otherwise}\\ \end{array}\right. } $$

where $Z = \{u \in X \cup Y \mid deg(u) = 1\}$.

Proof

Let $G=(X \cup Y,E)$ be a biconvex bipartite graph. Let $\sigma =x_1,x_2,\ldots ,x_p$ be an enumeration of vertices of X and $\pi =y_1,y_2,\ldots ,y_q$ be an enumeration of vertices of Y. Let Z represent the set of degree one vertices in G. We will divide the proof into the following cases depending on the existence of degree one vertices in X and Y.

Case 1: $|Z| = 0$. That is $\delta (G) \ge 2$.

Let $c: V(G) \rightarrow \{1,2,3\}$ be a coloring of G defined as follows: $c(x_i)=1$ for each $i \in [p]$, $c(y_j)=2$ when j is even and $c(y_j)=3$ otherwise for each $j \in [q]$. Clearly c is a proper coloring. Next, we show that c is a lid-coloring of G.

Consider two adjacent vertices $u\in X$ and $v\in Y$. Clearly $N[u] \ne N[v]$, otherwise $G=K_2$, contradicting the assumption that G is connected and has at least three vertices. Hence, we have $N[u] \ne N[v]$ for any pair of adjacent vertices of G. As $deg(u) \ge 2$, we have $c(N[u]) = \{1,2,3\}$ and $c(N[v]) = \{1,c(v)\}$. That is $c(N[u]) \ne c(N[v])$ for any pair of adjacent vertices u and v of G. Therefore, c is a lid coloring of G.

Case 2: Either $Z \cap X \ne \emptyset$ or $Z \cap Y \ne \emptyset$ but not both.

Without loss of generality we assume that $Z \cap X = \emptyset$ and $Z \cap Y \ne \emptyset$. It is easy to see that the coloring $c: V(G) \rightarrow \{1,2,3\}$ defined in Case 1 is also a lid-coloring of G in this case.

Case 3: Both $Z \cap X \ne \emptyset$ and $Z \cap Y \ne \emptyset$.

Suppose $\chi _{lid}(G)=3$ and let $f:V(G) \rightarrow [3]$ be a lid-coloring of G. Let $x \in Z \cap X$ and y be the neighbor of x. Without loss of generality, assume that $f(x) = 1$, $f(y) = 2$ and $f(N[x])=\{1,2\}$. Then $f(N[y])=\{1,2,3\}$, since G is connected and has at least three vertices. If $z \in N(y)$, then $f(N[z]) \ne \{1,2,3\}$, otherwise $f(N[y]) = f(N[z])$ and $N[y] \ne N[z]$. Thus, $f(N[z]) = \{2, f(z)\}$ for every $z \in N(y)$. Note that z is at even distance from x and y is at odd distance from x. Thus for any vertex w, $|f(N[w])|=3$ if w is at odd distance from x and $|f(N[w])|=2$ if w is at even distance from x. Every vertex v in the set $Z \cap Y$ is at odd distance from x, that is $|f(N[v])|=3$, which is a contradiction to the fact that the degree of v is one in G. Therefore $\chi _{lid}(G) \ge 4$. It was shown in [2] that $\chi _{lid}(G) \le 4$ when G is bipartite. Hence, we conclude that $\chi _{lid}(G) = 4$.    $\square$

Corollary 2

Given a biconvex bipartite graph G, the lid-chromatic number of G can be computed in polynomial time.

Proof

Given a biconvex bipartite graph $G=(X \cup Y,E)$, from Theorem 3 we only need to determine whether both X and Y contain degree one vertices or not which can be done in polynomial time. Based on this we decide the lid-chromatic number of G.    $\square$

6 Cartesian Product

Definition 3

(Cartesian product). Cartesian product $G\square H$ of graphs G and H is a graph such that $V(G\square H) = V(G) \times V(H)$, where $\times$ represents cartesian product and two vertices $(u_1,v_1)$ and $(u_2,v_2)$ in $G\square H$ are adjacent if and only if either $u_1 = u_2$ and $v_1$ is adjacent to $v_2$ in H, or $v_1 = v_2$ and $u_1$ is adjacent to $u_2$ in G.

Theorem 4

([2]). If G and H are bipartite graphs without isolated vertices, then $\chi _{lid}(G\square H) = 3$.

As a corollary, we obtain the lid-chromatic number of Cartesian product of paths.

Corollary 3

For every pair of integers m and n, where $2 \le m \le n$, we have $\chi _{lid}(P_m\square P_n) = 3$.

Taking the work forward, we study lid-coloring of Cartesian product of a path and a cycle, and Cartesian product of two cycles.

6.1 Cartesian Product of a Cycle and a Path

Theorem 5

For every pair of integers m and n, where $m \ge 3$, $n \ge 2$, we have

$$ \chi _{lid}(C_m \square P_n)= {\left\{ \begin{array}{ll} 5&{} m=3\text { and }n \ge 2\\ 4&{} m\text { is odd, }m >3\text { and }n \ge 2\\ 3&{} m\text { is even and }n \ge 2\\ \end{array}\right. } $$

Proof

Let $G = C_m \square P_n$ and let $V(C_3) = \{u_1, u_2,u_3\}$, $V(P_n) = \{v_1,v_2,\cdots ,v_n\}$ and $V(C_3 \square P_n)=\{(u_1,v_i), (u_2, v_i), (u_3, v_i)~|~ i \in [n]\}$.

Case 1: When $m=3$ and $n \ge 2$. A 5-lid-coloring of $C_3 \square P_n$ is given in the Fig. 2a. Hence, we have $\chi _{lid}(C_3 \square P_n) \le 5$.

Next, we show that $\chi _{lid}(C_3 \square P_n) \ge 5$. Let $X=\{(u_1,v_1), (u_2, v_1), (u_3, v_1)\}$. Clearly the graph $G[X] \cong C_3$. Hence $\chi _{lid}(G[X]) = 3$. Observe that (a) every pair of vertices in X have distinct closed neighborhoods and (b) all the three colors used in X in any lid-coloring of $C_3 \square P_n$ appear in the neighborhood of any vertex of X. In order to maintain distinct colors in their closed neighborhood, we must use at least two new colors in $\{(u_1,v_2), (u_2, v_2), (u_3, v_2)\}$. Therefore, any lid-coloring of $C_3 \square P_n$ must use at least 5 colors. Hence, we have $\chi _{lid}(C_3 \square P_n) = 5$.

Case 2: $m > 3$ and m is odd, $n\ge 2$.

Let $V(C_m) = \{u_1, u_2, \cdots , u_m\}$ and $V(P_n) = \{v_1,v_2,\cdots ,v_n\}$, and $V(C_m \square P_n)=\{(u_i,v_j)~|~ i \in [m], j \in [n]\}$. A 4-lid-coloring of $C_m \square P_n$ is given in the Fig. 2b. Hence, we have $\chi _{lid}(C_m \square P_n) \le 4$.

Next, we show that $\chi _{lid}(C_m \square P_n) \ge 4$. Let $X=\{(u_i,v_1)~|~i \in [m]\}$. As the graph G[X] induced by the vertices of X is an odd cycle, we have $\chi _{lid}(G) \ge \chi (G[X]) \ge 3$. Observe that in any proper coloring $f: V(G[X]) \rightarrow \{1,2,3\}$ there exists two adjacent vertices $(u_i,v_1)$ and $(u_j,v_1)$ such that $f(N[(u_i,v_1)])=f(N[(u_j,v_1)])=\{1,2,3\}$ in G[X]. As $N[(u_i,v_1)]\ne N[(u_j,v_1)]$, in any lid-coloring of G at least one new color must be used to color a vertex of either $N[(u_i,v_1)]$ or $N[(u_j,v_1)]$. Hence $\chi _{lid}(C_m \square P_n) \ge 4$. Altogether we have $\chi _{lid}(C_m \square P_n) = 4$.

Case 3: m is even and $n \ge 2$,

In this case both $C_m$ and $P_n$ are bipartite and hence from Theorem 4 we have $\chi _{lid}(C_m \square P_n)=3$.    $\square$

Fig. 2.

(a) A 5-lid-coloring of $C_3 \square P_n$ for $n \ge 2$, and (b) A 4-lid-coloring of $C_m \square P_n$, when m is odd, $m > 3$ and $n \ge 2$.

6.2 Cartesian Product of Two Cycles

Theorem 6

($\star$).  For every pair of integers m and n, where $m \ge 3$, $n \ge 3$, we have

$$ \chi _{lid}(C_m \square C_n)= {\left\{ \begin{array}{ll} 5&{} m=3\text { and }n \ge 3\\ 3&{} m\text { is even and }n\text { is even}\\ 4&{} m\text { is odd, }m>3\text { and }n\text { is even }\\ \le 5&{} m\text { is odd, }m>3\text { and }n\text { is odd, }n > 3\\ \end{array}\right. } $$

7 Lexicographic Product

Definition 4

(Lexicographic product). Lexicographic product G[H] of graphs G and H is a graph such that $V(G[H]) = V(G) \times V(H)$, where $\times$ represents cartesian product and two vertices $(u_1,v_1)$ and $(u_2,v_2)$ in G[H] are adjacent if and only if either $u_1$ is adjacent to $u_2$ in G, or $u_1 = u_2$ and $v_1$ is adjacent to $v_2$ in H.

Definition 5

A lid coloring $f:V(H) \rightarrow [k]$ of a graph H is called ‘bad’ if there exists a vertex v in H such that $f(N[v])=[k]$. Otherwise, we call f as a ‘good’ lid-coloring of H.

Theorem 7

($\star$).  Let H be a graph on n vertices with $\chi _{lid}(H)=k$. For any integer $m \ge 3$, we have

$$ \chi _{lid}(P_m[H]) = {\left\{ \begin{array}{ll} 2k+1 &{}\text {if }m\text { is odd and every }k\text {-lid-colring of }H\text { is bad ;} \\ 2k+2 &{}\text {if }m\text { is even and every }k\text {-lid-colring of }H\text { is bad ;} \\ 2k &{}\text {otherwise;} \\ \end{array}\right. } $$

8 Conclusion

In this paper, we have studied the lid-coloring of graphs. We have given the characterization of graphs having lid-chromatic number equals to the number of vertices. We have shown that, for any block graph G, $\chi _{lid}(G) \le 2 \chi (G)$. We have proved that lid-coloring is solvable in polynomial time on biconvex bipartite graphs. We have given the exact values of lid-chromatic number for the Cartesian and Lexicographic products of paths and cycles.

We conclude the paper with the following open problems.

• 1. If $\chi _{lid}(H)=k$ and every k-lid-coloring of H is ‘bad’ then what is the lid-chromatic number of (a) $P_2[H]$ (b) $C_3[H]$?

• 2. When both m and n are odd, we have showed that $4 \le \chi _{lid}(C_m \square C_n) \le 5$. We do not know the exact value of the lid-chromatic number of $C_m \square C_n$.