On the injective chromatic number of graphs (Q1849923)

A vertex \(k\)-coloring of a graph is said to be injective if its restriction to the neighbourhood of any vertex is injective. The injective chromatic number of a graph \(G\) is the least \(k\) such that there is an injective \(k\)-coloring of \(G\). In this paper some upper and lower bounds in general, plus some exact values are given. In particular, the injective chromatic number of the hypercube is explored in the context of previous work on similar concepts, especially the theory of error-correcting codes. Necessary and sufficient conditions for the injective chromatic number to be equal to the degree for a regular graph are proposed and it is shown that the problem of determining whether there exists an injective \(k\)-coloring of a graph \(G\) is NP-complete for every fixed \(k\geq 3\).