An injective coloring of a given graph \(G = (V, E)\) is a vertex coloring of \(G\) such that any two vertices with a common neighbor receive distinct colors. An \(e\)-injective coloring of a graph \(G\) is a vertex coloring of \(G\) in which any two vertices \(v, u\) with a common edge \(e\) (\(e \neq uv\)) receive distinct colors; in other words, any two end vertices of a path \(P_4\) in \(G\) achieve different colors. With this new definition, we want to take a review of injective coloring of a graph from the new point of view. For this purpose, we review the conjectures raised so far in the literature of injective coloring and \(2\)-distance coloring, from the new approach of \(e\)-injective coloring. Additionally, we prove that, for disjoint graphs \(G, H\), with \(E(G) \neq \emptyset\) and \(E(H) \neq \emptyset\), \(\chi_{ei}(G \cup H) = \max\{\chi_{ei}(G), \chi_{ei}(H)\}\) and \(\chi_{ei}(G \vee H) = |V(G)| + |V(H)|.\) The \(e\)-injective chromatic number of \(G\) versus the maximum degree and packing number of \(G\) is investigated, and we denote \(\max\{\chi_{ei}(G), \chi_{ei}(H)\} \leq \chi_{ei}(G \square H) \leq \chi_{2}(G)\chi_{2}(H).\) Finally, we prove that, for any tree \(T\) (\(T\) is not a star), \(\chi_{ei}(T) = \chi(T),\) and we obtain the exact value of the \(e\)-injective chromatic number for some specified graphs.
Graph coloring has many applications in various fields of life, such as timetabling, scheduling daily life activities, scheduling computer processes, registering allocations to different institutions and libraries, manufacturing tools, printed circuit testing, routing and wavelength, bag rationalization for a food manufacturer, satellite range scheduling, and frequency assignment. These are many applications that are out there right now and many more come in the follow.
A proper \(k\)-coloring (hereafter \(k\)-coloring) of a graph \(G\) is a function \(f:V(G)\rightarrow \lbrace 1,2,3,\dots,k \rbrace\) such that for all edge \(xy\in E\), \(f(x)\neq f(y)\). The chromatic number of \(G\), denoted by \(\chi(G)\), is the minimum integer \(k\) such that \(G\) has a \(k\)-coloring. There are many research works on the graph coloring parameters that is not possible to name all of them here. For instance see [4,17].
In \(1969\), Kramer and Kramer introduced the notion of \(2\)–distance coloring of a graph \(G\) or the usual proper coloring of \(G^2\) [9], we can some of its applications in [10]. A \(2\)–distance \(k\)-coloring of a graph \(G\) is a function \(f:V\rightarrow \lbrace 1,2,3,\dots,k \rbrace\), such that no pair of vertices at distance at most \(2\), receive the same color, in the other words, the colors of the vertices of all \(P_3\) paths in the graph are distinct. The \(2\)-distance chromatic number of \(G\), denoted by \(\chi_2(G)=\chi(G^2)\), is the minimum positive integer \(k\) such that \(G\) has a \(2\)-distance \(k\)-coloring. The \(2\)-distance coloring of \(G\), is a proper coloring [3,2,5].
For a graph \(G\), the subset \(S\) of \(V(G)\) is said to be a dominating set if any vertex \(x\in V\setminus S\) is adjacent to a vertex \(y\) in \(S\). A dominating set of \(G\) with minimum cardinality is called the domination number of \(G\) and is denoted by \(\gamma(G)\). A subset \(D\) of \(V(G)\) is said to be \(2\)-distance dominating set if any vertex \(d\in V\setminus D\), is in at most \(2\)-distance of to a vertex in \(D\). A \(2\)-distance dominating set of \(G\) with minimum cardinality is called the \(2\)-distance domination number of \(G\) and is denoted by \(\gamma_2(G)\).
The injective coloring was first introduced in \(2002\) by Hahn et al. [6] and it was also further studied in [1,8,11,12,15,16,18]. An injective \(k\)-coloring of a graph \(G\) is a function \(f:V\rightarrow \lbrace 1,2,3,\dots,k \rbrace\) such that no vertex \(v\) is adjacent to two vertices \(u\) and \(w\) with \(f(u)=f(w)\), in the other words, for any path \(P_3=xyz\), we have \(f(x)\neq f(z)\). The injective chromatic number of \(G\), denoted by \(\chi_i(G)\), is the minimum positive integer \(k\) such that \(G\) has an injective \(k\)-coloring. The injective chromatic number of the hypercube has important applications in the theory of error-correcting codes. As it is well known, the injective coloring of \(G\), is not necessarily proper coloring. Injective coloring of a graph \(G\) is related to the usual coloring of the square \(G^2\). The inequality \(\chi_i(G)\le \chi_2(G)\) obviously holds.
There are several results related to injective coloring that review the usual coloring results in graph theory from a new point of view, in particular on the injective chromatic number of planar graphs. As well, many conjectures on planar graphs have been posed and studied by authors so far. In this regard, we bring up some of them as follows.
From the relation between the injective coloring of a graph \(G\) and the usual coloring of the square \(G^2\), Wegner [19] posed the following conjecture.
1. \(\chi(G^2)\le 7\ \) if \(\Delta=3\),
2. \(\chi(G^2)\le\Delta+5\ \) if \(4 \le \Delta \le 7\),
3. \(\chi(G^2)\le \lfloor\frac{3}{2} \Delta\rfloor + 1\ \) otherwise.
Lužar and Škrekovski in [11] showed that:
1. \(\chi_i(G)=5\ \) if \(\Delta=3\),
2. \(\chi_i(G)=\Delta+5\ \) if \(4 \le \Delta \le 7\),
3. \(\chi_i(G)=\lfloor\frac{3}{2} \Delta\rfloor + 1\ \) if \(\Delta \ge 8\).
Adapted from Theorem 1.2, they proposed the following Wegner type conjecture for the injective chromatic number of planar graphs.
(i). \(\chi_i(G)\le 5\ \) if \(\Delta=3\),
(ii). \(\chi_i(G)\le \Delta+5\ \) if \(4 \le \Delta \le 7\),
(iii). \(\chi_i(G)\le \lfloor\frac{3}{2} \Delta\rfloor + 1\ \) otherwise.
By the relation between injective chromatic number and \(2\)-distance chromatic number of a graph; showing the truth of Conjecture 1.1 (parts (2), (3)), will deduce the truth of Conjecture 1.3 (parts (ii), (iii)).
Now we introduce a new concept of vertex coloring (near to injective coloring) as an \(e\)-injective coloring of a graph. The motivation of the alleging is to study, how it behaves against of the injective graph coloring, usual graph coloring, \(2\)-distance graph coloring, packing set, dominating set and \(2\)-distance dominating set of graphs. As well, in particular we investigate the posed conjectures from the point of view of \(e\)-injective colorings. Also since the notion of \(e\)-injective coloring is near to injective coloring, one can predict, it has applications in various fields of life in real world and would also be useful in coding theory as so did injective coloring.
This concept is introduced in next definition.
Hereafter, we say that, two vertices \(u,v\) have a common edge neighbor if there exist an edge \(e\) in which, \(u\) is adjacent to one end vertex of \(e\) and \(v\) is adjacent to another end vertex of \(e\).
The \(e\)–injective chromatic number of \(G\), denoted by \(\chi_{ei}(G)\), is the minimum positive integer \(k\) such that \(G\) has an \(e\)-injective \(k\)-coloring.
The \(e\)-injective coloring of \(G\), is not necessarily proper coloring. This concept can be expressed as new discourse.
Taking into account, the fact that a vertex subset \(S\) is independent in \(S_{3}(G)\) if and only if there is no path of length \(3\) between any two vertices corresponding of \(S\) in \(G\), we can readily observe that: \[\chi_{ei}(G)=\chi(S_{3}(G)).\]
From the point of view of \(e\)-injective coloring, the type of Conjectures 1.1 and 1.3 can be declared as a problem, which can be argued in next section.
1. \(\chi_{ei}(G)\le 5\ \) if \(\Delta=3\),
2. \(\chi_{ei}(G)\le \Delta+5\ \) if \(4 \le \Delta \le 7\),
3. \(\chi_{ei}(G)\le \lfloor\frac{3}{2} \Delta\rfloor + 1\ \) otherwise.
In the sequence, we assume that all graphs in this paper are finite, simple, and undirected. We use [4,20] as a reference for terminology and notation which are not explicitly defined here. Throughout the paper, we consider \(G=(V,E)\) be a finite simple graph with vertex set \(V=V(G)\) and edge set \(E=E(G)\). The open neighborhood of a vertex \(v\in V\) is the set \(N(v)=\lbrace u \lvert uv \in E \rbrace\), and its closed neighborhood is the set \(N[v]=N(v) \cup \lbrace v \rbrace\). The cardinality of \(\lvert N(v) \rvert\) is called the degree of \(v\), denoted by \(\deg(v)\). The minimum degree of \(G\) is denoted by \(\delta (G)\) and the maximum degree by \(\Delta (G)\). A vertex \(v\) of degree \(1\) is called a pendant vertex or a leaf, and its neighbor is called a support vertex. A vertex of degree \(n-1\) is called a full or universal vertex while a vertex of degree \(0\) is called an isolated vertex.
For any two vertices \(u\) and \(v\) of \(G\), we denote by \(d_G(u,v)\) the distance between \(u\) and \(v\), that is the length of a shortest path joining \(u\) and \(v\). The path, cycle and complete graph with \(n\) vertices are denoted by \(P_{n}\), \(C_{n}\) and \(K_{n}\) respectively. The complete bipartite graph with \(n\) and \(m\) vertices in their partite sets is denoted by \(K_{n,m}\), while the wheel graph with \(n+1\) vertices is denoted by \(W_{n}\). A star graph with \(n+1\) vertices, denoted by \(S_{n}\), consists of \(n\) leaves and one support vertex. A double star graph is a graph consisting of the union of two star graphs \(S_{m}\) and \(S_{n}\), with one edge joining their support vertices; the double star graph with \(m+n+2\) vertices is denoted by \(S_{m,n}\).
The join of two graphs \(G\) and \(H\), denoted by \(G\vee H\), is the graph obtained from the disjoint union of \(G\) and \(H\) with vertex set \(V(G\vee H) =V(G)\cup V(H)\) and edge set \(E(G\vee H)= E(G)\cup E(H)\cup \{xy\ |\ x\in V(G),\ y\in V(H)\}\). A fan graph is a simple graph consisting of joining \(\overline{K}_{m}\) and \(P_{n}\); the fan graph with \(m+n\) vertices is denoted by \(F_{m,n}\). For two sets of vertices \(X\) and \(Y\), the set \([X,Y]\) denotes the set of edges \(e=uv\) such that \(u\in X\) and \(v\in Y\).
The square graph \(G^{2}\) is a graph with the same vertex set as \(G\) and with its edge set given by \(E(G^{2})=\{uv| \ dist(u,v)\leq 2\}\). The chromatic number \(\chi(G^2)\) of \(G^{2}\) (or \(2\)-distance chromatic number \(\chi_2(G)\) of \(G\)) has been studied extensively in planar graph [7,14].
A subset \(B\subseteq V(G)\) is a
packing set in \(G\) if for every pair
of distinct vertices \(u, v\in B\),
\(N_{G}[u]\bigcap N_{G}[v]=\emptyset\).
The packing number \(\rho (G)\) is the
maximum cardinality of a packing set in \(G\).
A subset \(B\subseteq V(G)\) is an open
packing set in \(G\) if for every pair
of distinct vertices \(u, v\in B\),
\(N_{G}(u)\bigcap N_{G}(v)=\emptyset\).
The open packing number \(\rho^{\circ}(G)\) is the maximum
cardinality among all open packing sets in \(G\).
Let \(G\) and \(H\) be simple graphs. For three standard products of graphs \(G\) and \(H\), the vertex set of the product is \(V(G)\times V(H)\) and their edge set is defined as follows:
In the Cartesian product \(G\square H\), two vertices are adjacent if they are adjacent in one coordinate and equal in the other.
In the direct product \(G\times H\), two vertices are adjacent if they are adjacent in both coordinates.
The edge set of the strong product \(G\boxtimes H\), is the union of \(E(G\square H)\) and \(E(G\times H)\).
In the end of this section, we explore the purpose of the paper as follows. In Section 2, we study \(\chi_{ei}(G)\) versus to the \(\chi(G)\), \(\chi_{2}(G)\) and \(\chi_{i}(G)\), as well, we review the conjectures raised so far in the literature of injective and \(2\)-distance colorings, from the new approach, \(e\)-injective coloring, and by disproving the Problem 1.6, we show that the Conjectures 1.1 and 1.3 maybe wrong under the conditions. For disjoint graphs \(G, H\), with non-empty edge sets, \(\chi_{ei}(G\cup H)=max\{\chi_{ei}(G), \chi_{ei}(H)\}\) and \(\chi_{ei}(G\vee H)=|V(G)|+ |V(H)|\). The \(e\)-injective chromatic number of \(G\) versus of the maximum degree and packing number of \(G\) is investigated, and denote \(max\{\chi_{ei}(G), \chi_{ei}(H)\} \leq \chi_{ei}(G\square H)\leq \chi_{2}(G)\chi_{2}(H)\) in Section 3. In Section 4, we prove that, for any tree \(T\) (\(T\neq S_n\)), \(\chi_{ei}(T)=\chi(T)\), and we obtain the exact value of \(e\)-injective chromatic number of some special graphs and finally, we end the paper with discussion on research problems.
We maybe cannot compare \(\chi_{ei}(G)\) with \(\chi(G)\), \(\Delta(G)\), \(\chi_i(G)\) or \(\chi_2(G)\) in general. For instance, \(\chi_{ei}(K_3)=1\) while \(\chi(K_3)=3=\chi_i(K_3)=\chi_2(G)\); or \(\chi_{ei}(K_{1,n})=1\) while \(\chi(K_{1,n})=2,\ \chi_i(K_{1,n})=n\) and \(\chi_2(K_{1,n})=n+1\). But in the Figure 1, \(\chi_{ei}(G)= 12\), \(\chi_{i}(G)\le7\), \(\chi_{2}(G)\le7\), \(\chi(G)= 3\).
Also let \(H=K_m\circledcirc K_n\) be a graph obtain from two complete graphs \(K_m\) and \(K_n\) (\(m\ge n\ge 4\)) with joining one vertex of \(K_m\) to one vertex of \(K_n\). Then \(\chi(H)=m=\chi_{i}(H)\), \(\chi_{2}(H)=m+1\) and \(\chi_{ei}(H)=m+n-1\) (see Proposition 4.4). On the other hand, for Complete graph \(K_n\) (\(n\ge 4\)), odd cycle \(C_{3k}\) for odd \(k\ge 1\), we have \(\chi_{ei}(K_n)=n=\chi(K_n)=\chi_{i}(K_n)=\chi_{2}(K_n)\), and \(\chi_{ei}(C_{3k})=3=\chi(C_{3k})=\chi_{i}(C_{3k})=\chi_{2}(C_{3k})\).
In the same way, we have \(\Delta(K_3)=2\), \(\Delta(H)=m\), and for graph \(G\) in Figure 1, \(\Delta(G)=4\), while \(\chi_{ei}(K_3)=1\), \(\chi_{ei}(H)=m+n-1\), and \(\chi_{ei}(G)=12\). On the other hand, for graph \(K_n\circledcirc K_1\) (\(n\ge 4\)) and even cycle \(C_{2k}\), we have \(\chi_{ei}(K_n\circledcirc K_1)=n =\Delta(K_n\circledcirc K_1)\), and \(\chi_{ei}(C_{2k})= 2=\Delta(C_{2k})\) (see Proposition 4.3).
However we have the following.
Conversely, if any two end vertices of each path \(P_4\) in \(G\) are adjacent, then \(\chi_{ei}(G) \le \chi(G)\).
Proof. Since any two adjacent vertices of given graph \(G\) are the end vertices of a path \(P_4\) in \(G\), these two vertices must be colored with distinct colors by any \(e\)-injective coloring. Therefore, any \(e\)-injective coloring for this graph can be a usual coloring. Then \(\chi(G) \le \chi_{ei}(G)\).
Conversely, by the construction of graph \(G\), usual coloring of \(G\) deduces that any two end vertices of each path \(P_4\) has different colors. Thus, the usual coloring of given \(G\) is an \(e\)-injective coloring. Therefore, \(\chi_{ei}(G) \le \chi(G)\). ◻
Conversely, if end vertices of each path \(P_4\) in a graph \(G\) have a common neighbor, then \(\chi_{ei}(G) \le \chi_{i}(G)\).
Proof. Since any two vertices of graph \(G\) are the end vertices of a path \(P_4\), these vertices have distinct colors by \(e\)-injective coloring. Therefore, an \(e\)-injective coloring for this graph is an injective coloring. Then \(\chi_{i}(G) \le \chi_{ei}(G)\).
Conversely, let any two end vertices of path \(P_4\) have a common neighbor. Then by injective coloring of \(G\), two end vertices of any path \(P_4\) take different colors. Thus, this will be an \(e\)-injective coloring of \(G\) and \(\chi_{ei}(G) \le \chi_{i}(G)\). ◻
Also, we may have.
Conversely, if \(G\) is a graph and any two end vertices of each path \(P_4\) in \(G\) are adjacent or have a common neighbor, then \(\chi_{ei}(G) \le \chi_{2}(G)\).
Proof. Let \(v, u, w\) be three vertices of \(P_3\) in \(G\). Since both of them are the end vertices of a path \(P_4\) in \(G\), then \(e\)-injective coloring of the given graph \(G\) assign three distinct colors to \(v, u, w\). This implies that, this coloring is a \(2\)-distance coloring of \(G\). Thus, \(\chi_{2}(G) \le \chi_{ei}(G)\).
Conversely, let any two end vertices of each path \(P_4\) are adjacent or have a common neighbor. Then, from a \(2\)-distance coloring of \(G\), we deduce that, any two end vertices of the path \(P_4\) are vertices of a \(P_2\) or a \(P_3\) in graph \(G\) and so their colors are distinct. Therefore this coloring is an \(e\)-injective coloring of the given graph \(G\) and \(\chi_{ei}(G) \le \chi_{2}(G)\). ◻
Now we discuss on the Problem 1.6. Below figures denote that the Problem 1.6 is not necessarily true. On the other hand the type of Conjectures 1.1, 1.3 are not true for \(e\)-injective coloring. But if we use the Propositions 2.2, 2.3, then maybe characterize graphs \(G\) in which, satisfy on the Conjectures 1.1, 1.3 and also characterize graphs \(G\) in which, the Conjectures 1.1, 1.3 are not true for them.
Disprove of Problem 1.6 Let \(G\) be a planar graph with maximum degree \(\Delta\). Then we present counterexample that denote the Problem 1.6 is not true.
As we observe the Figure 2, for (\(3\le \Delta \le 8\)) we have.
The graph \(M_3\) denotes a planar graph in which \(\Delta(M_3)=3\) and \(\chi_{ei}(M_3)=6> 5\).
The graph \(M_4\) denotes a planar graph in which \(\Delta(M_4)=4\) and \(\chi_{ei}(M_4)=12> \Delta(M_4)+5\).
The graph \(M_5\) denotes a planar graph in which \(\Delta(M_5)=5\) and \(\chi_{ei}(M_5)=13 > \Delta(M_5)+5\).
The graph \(M_6\) denotes a planar graph in which \(\Delta(M_6)=6\) and \(\chi_{ei}(M_6)=16> \Delta(M_6)+5\).
The graph \(M_7\) denotes a planar graph in which \(\Delta(M_7)=7\) and \(\chi_{ei}(M_7)=16> \Delta(M_7)+5\).
For \(\Delta(G)= 8\), consider the graph \(M_8\) of order \(16\), which is seen \(\Delta(G)=8\) and \(\chi_{ei}(M_n)=16> \lfloor \frac{24}{2} \rfloor+1=13= \lfloor \frac{3\Delta}{2} \rfloor+1\).
For \(\Delta(G)\ge 9\) consider, the graph \(M_n\) (\(n\ge 9\)) of order \(2n\), Figure 2, which is seen \(\Delta(G)=n\) and \(\chi_{ei}(M_n)=2n> \lfloor \frac{3n}{2} \rfloor+1 =\lfloor \frac{3\Delta}{2} \rfloor+1\).
With this regard, the Problem 1.6 is disproved. In the other words the type of Conjecture 1.3 for \(e\)-injective coloring is rejected. However, from the Propositions 2.2 and 2.3, we can have.
2. Let \(G\) be a graph with the property that the given data in Proposition, 2.2 (Conversely part) hold. Then, the Conjecture 1.3 is wrong.
In this section we prove some results on \(e\)-injective coloring using some operations.
For graphs \(G\) and \(H\), let \(G\cup H\) be the disjoint union of \(G\) and \(H\). Then it is easy to see that \(\chi_{ei}(G\cup H) = max\{\chi_{ei}(G), \chi_{ei}(H)\}\).
For the join of two graphs, we have the following.
Proof. Let \(e_1=v_1w_1\in E(G)\) and \(e_2=v_2w_2\in E(H)\) be two edges. We show that any two vertices \(x, y\) in \(G\vee H\), there is a path of length \(3\), with end vertices \(x,y\). For observing the result, we bring up five positions.
1. For \(x, y\in V(G)\), consider the path \(xv_2w_2y\) in \(G\vee H\).
2. For \(x, y\in V(H)\), consider the path \(xv_1w_1y\) in \(G\vee H\).
3. For \(x\in V(G)\setminus \{v_1,w_1\}\) and \(y\in V(H)\setminus \{v_2,w_2\}\), consider the path \(xv_2v_1y\) in \(G\vee H\).
4. For \(x\in \{v_1,w_1\}\), say \(v_1\) and \(y\in V(H)\setminus \{v_2,w_2\}\), consider the path \(v_1v_2w_1y\) in \(G\vee H\).
5. For \(x\in \{v_1,w_1\}\) and \(y\in\{v_2,w_2\}\) and without loss of generality, say \(x=v_1\) and \(y=v_2\), consider the path \(v_1w_1w_2v_2\) in \(G\vee H\).
The other positions are similar. Therefore, for any two vertices \(x,y \in G\vee H\) there is a path of length \(3\), with end vertices \(x,y\). Therefore the result is observed. ◻
Let \(G\) be a graph and \(B\) be a maximum packing set of \(G\). If \(v\in V(G)\setminus B\), then there is a vertex \(u\in B\) such that \(N(v)\cap N(u)\ne \emptyset\). This shows that, \(d(v,u)\le 2\). Thus \(B\) is a \(2\)-distance dominating set. Therefore we have.
Proof. Let \(B\) be maximum
packing set of graph \(G\). Since two
vertices of \(B\) has distance \(3\), they are assigned with two distinct
colors. Thus \(\chi_{ei}(G)\ge
\rho\).
For equalities, consider the cycles \(C_6\) and \(C_8\), (see Propositions 4.3). ◻
We now give an upper bound on \(\chi_{ei}(G)\) that may be slightly important.
Proof. Let \(G\) be a graph
and \(v \in V(S_3(G))=V(G)\). It is
well known that there are at most \(\Delta(\Delta-1)^2\) vertices in \(G\) such that any of them with \(v\) form two end vertices of path \(P_4\). This shows that \(\deg_{S_{3(G)}}(v)\le \Delta(\Delta-1)^2\).
On the other hand \(\chi_{ei}(G)=
\chi(S_3(G))\) and from Brooks Theorem in usual coloring of
graphs, \(\chi(S_3(G))\le \Delta(S_3(G))+1\le
\Delta(\Delta-1)^2+1\). Therefore \(\chi_{ei}(G)\le
\Delta(\Delta-1)^2+1\).
For seeing the sharpness observe Proposition 4.3. ◻
Also we want to drive bounds for the \(e\)-injective coloring of Cartesian product of two graphs \(G\), \(H\) in terms of \(2\)-distance coloring of the of \(G\) and \(H\). For this we explore a result from [13] and a lemma.
Proof. Suppose that the end vertices of each path \(P_4\) in graphs \(G\) and \(H\) are adjacent or have a common neighbor.
We would to be show any two end vertices of a path \(P_4\) in \(G\boxtimes H\) are adjacent or have a
common neighbor. For this, we can bring up the possible paths \(P_4\) in graph \(G\boxtimes H\).
1.1. \((a,u)(a,v)(a,w)(a,t)\); 1.2.
\((a,u)(a,v)(a,w)(b,w)\); 1.3. \((a,u)(a,v)(a,w)(b,t)\).
2.1. \((a,u)(a,v)(b,v)(b,w)\); 2.2. \((a,u)(a,v)(b,v)(c,v)\); 2.3 \((a,u)(a,v)(b,v)(c,w)\).
3.1. \((a,u)(a,v)(b,w)(b,t)\); 3.2. \((a,u)(a,v)(b,w)(c,w)\); 3.3. \((a,u)(a,v)(b,w)(c,t)\).
4.1. \((a,u)(b,u)(b,v)(b,w)\); 4.2. \((a,u)(b,u)(b,v)(c,v)\); 4.3. \((a,u)(b,u)(b,v)(c,w)\).
5.1. \((a,u)(b,u)(c,u)(c,v)\); 5.2. \((a,u)(b,u)(c,u)(d,u)\); 5.3. \((a,u)(b,u)(c,u)(d,v)\).
6.1. \((a,u)(b,u)(c,v)(c,w)\); 6.2. \((a,u)(b,u)(c,v)(d,v)\); 6.3. \((a,u)(b,u)(c,v)(d,w)\).
7.1. \((a,u)(b,v)(b,w)(b,t)\); 7.2. \((a,u)(b,v)(b,w)(c,w)\); 7.3. \((a,u)(b,v)(b,w)(c,t)\).
8.1. \((a,u)(b,v)(c,v)(c,w)\); 8.2. \((a,u)(b,v)(c,v)(d,v)\); 8.3. \((a,u)(b,v)(c,v)(d,w)\).
9.1. \((a,u)(b,v)(c,w)(d,w)\); 9.2.
\((a,u)(b,v)(c,w)(c,t)\); 9.3. \((a,u)(b,v)(c,w)(d,t)\).
Now we observe that, all these paths type \(P_4\) are adjacent or have a common
neighbor.
1.1. Since \(uvwt\) is a path \(P_4\) in \(H\), the vertices \(u\) and \(t\) are adjacent or have a common neighbor. If \(u\) and \(t\) are adjacent, then the vertices \((a,u)\) and \((a,t)\) are adjacent in \(G\boxtimes H\). If \(u\) and \(t\) have a common neighbor \(s\), then \((a,s)\) is a common neighbor of \((a,u)\) and \((a,t)\).
1.2. \((a,v)\) is a common neighbor of \((a,u)\) and \((b,w)\) in \(G\boxtimes H\).
1.3. The \(uvwt\) is a path \(P_4\) in \(H\). If \(u\) and \(t\) are adjacent, then the vertices \((a,u)\) and \((b,t)\) are adjacent in \(G\boxtimes H\). If \(u\) and \(t\) have a common neighbor \(s\), then \((a,s)\) is a common neighbor of \((a,u)\) and \((b,t)\).
2.1. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((b,w)\) in \(G\boxtimes H\).
2.2. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,v)\) in \(G\boxtimes H\).
2.3. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,w)\) in \(G\boxtimes H\).
3.1. Its proof is readily and similar to the proof of 1.3.
3.2. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,w)\) in \(G\boxtimes H\).
3.3. Its proof is readily, and is similar to the proof of 1.3.
4.1. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((b,w)\) in \(G\boxtimes H\).
4.2. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,v)\) in \(G\boxtimes H\).
4.3. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,w)\) in \(G\boxtimes H\).
5.1. The vertex \((b,u)\) is a common neighbor of \((a,u)\) and \((c,v)\) in \(G\boxtimes H\).
5.2. Since \(abcd\) is a path \(P_4\) in \(G\), the vertices \(a\) and \(d\) are adjacent or have a common neighbor. If \(a\) and \(d\) are adjacent, then the vertices \((a,u)\) and \((d,u)\) are adjacent in \(G\boxtimes H\). If \(a\) and \(d\) have a common neighbor \(r\), then \((r,u)\) is a common neighbor of \((a,u)\) and \((d,u)\).
5.3. Its proof is obvious and it is similar to the proof of 5.2.
6.1. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,v)\) in \(G\boxtimes H\).
6.2. Its proof is obvious and it is similar to the proof of 5.2.
6.3. Its proof is obvious and it is similar to the proof of 5.2.
7.1. Its proof is similar to the proof of 1.3.
7.2. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,w)\) in \(G\boxtimes H\).
7.3. Its proof is similar to the proof of 1.3.
8.1. The vertex \((b,v)\) is a common neighbor of \((a,u)\) and \((c,w)\) in \(G\boxtimes H\).
8.2. Its proof is similar to the proof of 5.2.
8.3. Its proof is similar to the proof of 5.2.
9.1. Its proof is similar to the proof of 5.2.
9.2. Its proof is similar to the proof of 1.3.
9.3. There are two paths \(abcd\) and \(uvwt\) in \(G\) and \(H\) respectively. If \(ad\in E(G)\) and \(ut\in E(H)\), then \((a,d)\) and \((u,t)\) are adjacent in \(G\boxtimes H\). If \(ad\in E(G)\) and \(s\) is a common neighbor of \(u\) and \(t\), then \((a,s)\) is a common neighbor of \((a,u)\) and \((d,t)\) in \(G\boxtimes H\). If \(ut\in E(H)\) and \(r\) is a common neighbor of \(a\) and \(d\), then \((r,u)\) is a common neighbor of \((a,u)\) and \((d,t)\) in \(G\boxtimes H\). If \(a\) and \(d\) have a common neighbor \(r\), and similarly, \(s\) is a common neighbor of \(u\) and \(t\), then \((r,s)\) is a common neighbor of \((a,u)\) and \((d,t)\) in \(G\boxtimes H\).
It is observed that, both end vertices of every path \(P_4\) in \(G\boxtimes H\) are adjacent or have a common neighbor. Therefore the proof is complete. ◻
Now we have the following.
Proof. For the first inequality, since \(G\) and \(H\) have no isolated vertices, and any path of length \(3\) of \(G\) and \(H\) gives at least one path of length \(3\) of \(G\square H\), thus the first inequality holds. For seeing the sharpness, consider \(G=P_m\) and \(H=P_n\) where \(m\ge 4\) or \(n\ge 4\).
We now prove the second inequality. From the definitions of Cartesian and strong products, we may have \(G\square H\) as a subgraph of \(G\boxtimes H\), and next any path \(P_4\) of \((G\square H)\) is a path \(P_4\) of \((G\boxtimes H)\). Therefore, \(\chi_{ei}(G\square H)\leq \chi_{ei}(G\boxtimes H)\). As the same way, \(\chi_{2}(G\square H)\leq \chi_{2}(G\boxtimes H)\). From Proposition 2.3 and Lemma 3.5 \(\chi_{ei}(G\boxtimes H) \le \chi_{2}(G\boxtimes H)\). On the other hand, from Theorem 3.4, \(\chi_{2}(G\boxtimes H)\leq \chi_{2}(G)\chi_{2}(H)\). These deduce that \(\chi_{ei}(G\square H)\leq \chi_{2}(G)\chi_{2}(H)\). It is easy to see that, this bound is sharp for \(G=C_3\) and \(H=C_5\) and also \(G=C_3\) and \(H=C_7\). ◻
In this section we investigate the \(e\)-injective coloring of some special graphs, such as trees, path, cycle, complete graphs, wheel graphs, star, complete bipartite graphs, \(k\)-regular bipartite graphs, multipartite graphs and fan graphs.
1. \(\chi_{ei}(T)=1\) if and only if \(diam(T)\le 2\).
2. \(\chi_{ei}(T)=2\) if and only if \(diam(T)\ge 3\).
Proof. 1. If \(diam(T)=1\), then \(T=P_2\) and if \(diam(T)=2\), then \(T\) is a star and since there is no path of length \(3\) between any two vertices, \(\chi_{ei}(T)=1\).
Conversely, let \(\chi_{ei}(T)=1\). Then there is no path of length \(3\) in \(T\). Thus \(diam(T)\le 2\).
2. Let \(diam(T)\ge 3\) and \(v_0\) be a vertex of maximum degree in \(T\). We assign color \(1\) to the \(v_0\) and to the vertex \(u\) if \(d(u,v_0)\) is even, and color \(2\) to the vertex \(u\) if \(d(u,v_0)\) is odd. Since there is only one path between any two vertices in any tree \(T\), so if two vertices \(x,y\) are in distance \(3\) and two vertices \(x,z\) are in distance \(3\), then two vertices \(y,z\) are not in distance \(3\). This shows that, we can use color \(1\) for \(x\) and color \(2\) for \(y,z\). Therefore \(\chi_{ei}(T)\le 2\). On the other hand, if \(diam(T)\ge 3\), then \(\chi_{ei}(T)\ge 2\). Therefore, if \(diam(T)\ge 3\), then \(\chi_{ei}(T)=2\).
Conversely, if \(\chi_{ei}(T)= 2\), there is two vertices \(v,w\) in \(T\) so that the path \(vxyw\) is of length \(3\) in \(T\). This shows that \(diam(T)\ge 3\). ◻
As an immediate from Theorem 4.1 we have.
\[\chi_{ei}(P_n)=\begin{cases} 1 &\ \ n\leq3 ,\\ 2 &\ \ n\ge 4 .\\ \end{cases}\]
Proof. Let \(n=3\). It is obvious that \(\chi_{ei}(C_3)=1\).
Let \(n\ge 4\). There are two cases to be considered.
Case 1. If \(n\) is even.
We assign the color \(1\) to the odd vertices and color \(2\) to the even vertices. Therefore \(\chi_{ei}(C_{2k})=2\).
Case 2. If \(n\) is odd.
Let \(n=5\). We assign the color \(1\) to the vertices \(v_{1}, v_{2}\) and color \(2\) to the vertices \(v_{3},v_{4}\) and we assign color \(3\) to the vertex \(v_{5}\). This assignments is an \(e\)-injective coloring of \(C_{5}\).
Let \(n\geq 7\) . We assign the color \(1\) to the odd vertices \(v_i\)s, for \(i\le n-4\) and color \(2\) to the even vertices \(v_i\)s, for \(i\le n-3\) and we assign color \(3\) to the vertices \(v_{n-2}, v_{n-1}, v_n\). This assignments is an \(e\)-injective coloring of \(C_n\) for odd \(n\geq 7\). On the other hand, since there are two paths of length \(3\) between \(v_{n-2}\) with two vertices \(v_{1}\), \(v_{n-5}\), as well as \(v_{n-1}\) with two vertices \(v_{2}\), \(v_{n-4}\) and also \(v_{n}\) with two vertices \(v_{3}\), \(v_{n-3}\). It is clear that, one cannot \(e\)-injective color to the vertices cycle \(C_n\) withe two colors for odd \(n\). Therefore the result holds. ◻
Since for \(n\ge 4\), any two vertices of \(K_n\) are end of a path \(P_4\), then we have.
Proof. Let \(v_{1}\) be a universal vertex. For \(i,j\ge 2\), there exists a path \(v_jv_{j+1}v_1v_i\) between \(v_i\) and \(v_j\) if \(v_i\ne v_{j+1}\); and there exists a path \(v_jv_{1}v_{j+2}v_i\) between \(v_i\) and \(v_j\) if \(v_i= v_{j+1}\). On the other hand, there exists a path \(v_1v_{i-2}v_{i-1}v_i\) between \(v_1\) and \(v_i\). Taking this account, there exist a path of length \(3\) between two vertices in \(W_{n}\). Therefore \(\chi_{ei}(W_{n})=n+1\). ◻
Proof. Let \(n\geq2,\ m\geq2\). It is easy to observe that, there is a path of length \(3\) between two vertices of two different partite sets. Therefore one can assign color \(1\) to one partite set and \(2\) to another partite set. Thus, \(\chi_{ei}(K_{n,m})=2\). ◻
Using the proof of Proposition 4.6, For regular bipartite graphs, we have the next result, which proof is similar.
A complete \(r\) partite graph is a simple graph such that the vertices are partitioned to \(r\) independent vertex sets and every pair of vertices are adjacent if and only if they belong to different partite sets.
\[\chi_{ei}(G)=\begin{cases} 1, &\ \ r=3\ \text{ and }\ G=K_{1,1,1},\\ n-1, &\ \ r=3\ \text{ and }\ G\in \{K_{n-2,1,1}, K_{{1},n-2,1}, K_{{1},1, n-2}\}\ \text{ with }\ n\ge 4,\\ n, &\ \ otherwise. \end{cases}\]
Proof. 1. It is trivial.
2. Let \(r=3\) and \(G\in \{K_{n-2,1,1}, K_{{1},n-2,1}, K_{{1},1, n-2}\}\). Without loss of generality, assume that \(G=K_{n-2,1,1}\) with vertex set \(V=\{v_1,v_2,\dots, v_{n-2}, u_1, w_1\}\). The path \(v_iu_1w_1v_j\) is a path of length \(3\) between \(v_i, v_j\). The paths \(u_1v_iw_1v_j\) and \(w_1v_iu_1v_j\) are paths of length \(3\) between \(u_1, v_j\) and between \(w_1, v_j\) respectively. On the other hand, there exists no path of length \(3\) from \(u_1\) and \(w_1\). Now we can assign same color to \(u_1\), \(w_1\) and \(n-2\) other different colors to the \(v_i\)s. Thus \(\chi_{ei}(G)=n-1\).
3. If \(r\ge 4\), and \(v_i, w_j\) are two vertices of two partite sets, then taking two vertices from two other partite sets \(x_m, y_l\), one can construct a path \(v_i, x_m, y_l, w_j\) of length \(3\).
Let \(r=3\) and \(G=K_{k,l,m}\) where two of \(k,l,m\) are at least \(2\). If \(k=1\) and \(l,m\ge 2\) with \(V(G)=\{v_1, u_1\dots, u_l, w_1,\dots, w_m\}\), then \(v_1u_i w_s u_j\), \(v_1w_i u_s w_j\), \(u_iv_1u_jw_s\), \(u_iw_tv_1u_j\), \(w_iu_xv_1w_j\) with \(i\ne j\), give us a path of length \(3\) between \(v_1, u_j\), \(v_1, w_j\), \(u_i,w_s\), \(u_i,u_j\) and \(w_i,w_j\) respectively.
Let \(r=3\) and \(G=K_{k,l,m}\) where \(k,l,m\ge 2\). Then, similar to the second part of situation 3, there exist a path of length \(3\) between any two vertices of \(G\). Therefore \(\chi_{ei}(G)=n\). Thus the result holds. ◻
\[\chi_{ei}(F_{m,n})=\begin{cases} 1, &\ \ m=1,n=2 ,\\ m+1, &\ \ m\geq 2, n=2, \\ m+n, &\ \ m= 1, n\geq 4 \ \text{ and } \ m\geq 2, n\geq 3.\\ \end{cases}\]
Proof. There are three situations to be considered.
1. If \(m=1,n=2\). It is obvious.
2. If \(m\geq 2, n=2\) and \(V(F_{m,2})=\{v_1, v_2,\dots, v_m, u_1,u_2\}\), then by definition \(F_{2,2}\cong F_{1,3}\) and \(F_{m,2}=\overline{K}_{m}\vee P_{2}\). Two vertices \(u_1,u_2\) receive same color because there is no path of length \(3\) between them. On the other hand there exist a path \(v_iu_1u_2v_j\) of length \(3\) between any pair of vertices \(v_i,v_j\), and there exist a path \(v_iu_lv_ju_k\) with \(l\neq k\) of length \(3\) between any pair of vertices \(v_i,u_k\). Therefore \(\chi_{ei}(F_{m,2})=m+1\).
3.1. Let \(m= 1, n\geq 4\) and \(V(F_{1,n})=\{v_1, u_1,u_2,\dots, u_n\}\). Then \(v_1u_{i+2}u_{i+1}u_{i}\), (\(i\leq n-2\)), \(v_1u_{i-2}u_{i-1}u_{i}\), (\(i\geq n-1\)), \(u_{i}v_1u_{j+1}u_{j}\), (\(i<j<n\)), \(u_{i}v_1u_{n-1}u_{n}\) (\(i<n-1\)) and \(u_{n-1}u_{n-2}v_1u_{n}\) are the paths of length \(3\) between any pair of vertices \(u_i\), \(u_j\) and \(v_1\), \(u_i\). Thus \(\chi_{ei}(F_{1,n})=1+n\).
3.2. Let \(m\geq 2, n\geq 3\). Using the reasons given in proof of part 3.1, one can easy to see that there is a path of length \(3\) between any pair of vertices of \(F_{m,n}\).
All in all the proof is completed. ◻
From Propositions 2.1, 2.2 and 2.3,
1. Characterize graphs \(G\) with \(\chi_{ei}(G)=\chi(G)\); Characterize graphs \(G\) with \(\chi_{ei}(G)=\chi_i(G)\); Characterize graphs \(G\) with \(\chi_{ei}(G)=\chi_2(G)\).
2. After discussion on the solution of 1, one can revisit the
Conjectures 1.1 and 1.3.
From Propositions 3.3 and 3.2, we
can have the following.
3. Characterize graphs \(G\) with \(\chi_{ei}(G)=\rho(G)\).
4. Characterize graphs \(G\) with \(\chi_{ei}(G)=\Delta(G)(\Delta(G)-1)^2+1\).
1970-2025 CP (Manitoba, Canada) unless otherwise stated.