Let $G$ be a simple graph (finite or infinite), $[n]\mathrel{:=}\{1,...,n\}$. Define the function:
$$\varepsilon\_n(G)\mathrel{:=}\min\_\phi{\lvert{\operatorname{dom} (\phi)}\rvert},$$
where $\phi$ is the 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 \operatorname{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 to 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 the nodes of a graph and place symbols of inequality on the edges. 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 the undirected infinite graph such that $V(\mathbb{Z}\_G )= \mathbb{Z} $, and $E(\mathbb{Z}\_G)=\{(i,j)\in \mathbb{Z}^2\mathrel: i+1=j \}$.
It's clear that $\varepsilon\_n(\mathbb{Z}\_G) \neq 0 $ for all $n$, 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 \mathrm{FNP}$.



What is this invariant graph?
Rephrasing, given $G$ and $n$ you're looking for the smallest subset $V' \subseteq V$ of the vertices of $G$ such that the subgraph $G'$ induced by $V'$ has a vertex colouring $\phi$ on $n$ colours for which every pair of colours $c \neq d$ has an edge between those colours and there is no edge between two vertices of the same colour.


For your particular case of interest, when $n$ is odd we can colour a subchain of $\mathbb{Z}\_G$ in the sequence of colours of an Eulerian path on $K\_n$ to find that $\varepsilon\_n(\mathbb{Z}\_G) = \binom{n}{2} + 1$. When $n$ is even, $\varepsilon\_n(\mathbb{Z}\_G) = \binom{n}{2} + \frac{n-2}{2} + 1$ by a similar argument, as bof correctly pointed out in a comment improving the earlier claim of this answer: the addition of $\frac{n-2}{2}$ edges is necessary and sufficient for an Eulerian trace to exist.


