co.combinatorics – What is this invariant graph

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,yin(n),xneq y exists u,vin V(G): phi(u)=x, phi(v)=y,uv in E(G)$ and $forall u,vin dom(phi), uneq v,phi(u)=phi(v) implies uvnotin 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,mgeq 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$.