Инварианты графа

[Not_Al]

Здравствуйте. Рассмотрим следующую последовательность функций на не обязательно конечных неориентированных графах без петель и кратных ребер $(\varepsilon_n)_{n=1}^{\infty}$ :

$$\varepsilon_n(G)=\min\limits_{\varphi}\left\lvert \operatorname {dom} \varphi \right\rvert$$

, где минимум берется по всем $\varphi:V(G)\to\{1,...,n\}$ , что $\varphi$ - это частичная сюръективная функция, такая что $\varphi(p_1)=\varphi(p_2)\Rightarrow p_1p_2\notin E(G)$ , где $p_1,p_2\in V(G)$ и для любых различных $k_1,k_2\in\{1,...,n\}$ существует пара $p_1,p_2\in V(G)$ , что $\varphi(p_1)=k_1,\varphi(p_2)=k_2$,и $p_1p_2\in E(G)$. В случае, если такой частичной функции нет примем $\varepsilon_n(G)=0$.
Мой вопрос состоит в вычислении этих инвариантов. Я знаю, что $n\leqslant\varepsilon_n(G)\leqslant \left\lvert V(G) \right\rvert$ при ненулевых значениях $\varepsilon_n(G)$ и эти значения оптимальны: $\varepsilon_n(K_n)=n=\left\lvert V(G) \right\rvert$, где $K_n$ - полный граф на $n$ вершинах.
Также понятно, что если $\left\lvert V(G) \right\rvert<n$ , то $\varepsilon_n(G)=0$ .
Увы, также $\varepsilon_n(G)=n \Leftrightarrow K_n \subseteq G$ , значит вычисление $\varepsilon_n$ это сложная задача. Есть ли что-то помимо полного перебора отображений?