expand the number of cases in which the conjecture is satisfied. In addition, we propose an integer programming formulation for ACP which is used for checking the conjecture over all connected graphs up to 10 vertices.

Regular bipartite and complete multipartite graphs
==================================================

As far as we know, the conjecture has not been proved for bipartite graphs yet. We show that the conjecture holds for a subclass of bipartite graphs including regular ones, when its vertices have the same degree.

Let $G = (U \cup V, E)$ be a bipartite graph ($U$ and $V$ are its stable sets) such that, for all $v \in V$ and $u \in N(v)$, $d(u) < 2 d(v)$. If $d(u) \neq d(v)$ for all $(u,v) \in E$ then $\eta(G) = 1$, otherwise $\eta(G) = 2$.

In virtue of Observation \[ADDITIVE1\], we only have to prove $\eta(G) \leq 2$. Consider the assignment $f:V \rightarrow \{1,2\}$ such that $f(u) = 2$ for all $u \in U$ and $f(v) = 1$ for all $v \in V$. Then, $f(N(u)) = d(u) < 2 d(v) = f(N(v))$ for all $(u,v) \in E$.

\[REGULARBIP\] If $G$ is a regular bipartite graph, then $\eta(G) = 2$.

Now, we consider complete multipartite graphs. 