# 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)$$.
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$$.