Let $G$ is simple graph (finite or infinite), $[n]:=\{1,...,n\}$. Define next function: $$\varepsilon_n(G):=\min_\phi{|dom (\phi)|}$$ , where $\phi$ is partial function $\phi:V(G)\to[n]$, such that $\forall x,y\in[n],x\neq y \exists u,v\in V(G): \phi(u)=x, \phi(v)=y,uv \in E(G)$ and $\forall u,v\in dom(\phi), u\neq v,\phi(u)=\phi(v) \implies uv\notin E(G) $. I need information about this function, but I don't know where search. Intuitively, one can think of this function as the minimum number of characters we can write to express the inequality of $n$ numbers, if we place them on nodes of graph and place symbols of inequality on edge. It's obvious that $0 \leq \varepsilon_n(G) \leq v(G) $, $$\varepsilon_n(K_m)=\begin{cases}n,m\geq n\\0,m < n \end{cases}$$ In particular, I am interested in the values ​​of $\varepsilon_n(\mathbb{Z}_G)$ , where $\mathbb{Z}_G $ is undirected infinite graph, such that $V(\mathbb{Z}_G )= \mathbb{Z} $, and $E(\mathbb{Z}_G)=\{(i,j)\in \mathbb{Z}^2|i+1=j \}$. It's clear that $\forall n \;\varepsilon_n(\mathbb{Z}_G) \neq 0 $, but I have no rigorous proof of this statement. I am also interested in the complexity of calculating $ \varepsilon_n(G) $ in the general case, but I do not understand how not to iterate over many $\phi$. I think that $\varepsilon_n(G) \in FNP$.