What is this invariant graph?

Question

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}$.

Answer 1

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.