Let $G$ be a simple graph (finite or infinite), $[n]:=\{1,...,n\}$. Define the function: $$\varepsilon_n(G):=\min_\phi{|{\operatorname{dom} (\phi)}|},$$ 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: 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 FNP$.

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

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

Let $G$ be a simple graph (finite or infinite), $[n]:=\{1,...,n\}$. Define the function: $$\varepsilon_n(G):=\min_\phi{|{\operatorname{dom} (\phi)}|},$$ 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: 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 FNP$.