# Number of ways painting graph in two colors, such that two nodes of same color are linked by edge

We are given undirected graph of $$N$$ nodes and $$M$$ edges, we want to count the number of possible ways to paint this graph in $$2$$ colors such that for each two nodes having the same color, there must be an edge between them.

I tried some examples on paper and I always got numbers of the form $$2^x$$, however I couldn't see a valid way to find such $$x$$ or I couldn't prove why this is the case.

Does this problem become easier if we are given directed acyclic graph instead of undirected one?

• Besides $2^x$, it might be 0 as well, i.e., there might be no way. For example, a pentagon or a totally disconnected graph of three points. – John L. Jul 20 '19 at 8:03

Let $$G$$ be a given graph and $$G'$$ be the complement graph of $$G$$, i.e., $$G'$$ and $$G$$ are on the same nodes such that two distinct nodes of $$G'$$ are adjacent if and only if they are not adjacent in $$G$$.
An attractive-coloring of $$G$$ is an repulsive-coloring of $$G'$$ and vise versa. So the number of attractive-2-colorings of $$G$$ is the number of repulsive-2-colorings of $$G'$$. Note that a 1-coloring is considered a 2-coloring.
Suppose the connected components of $$G'$$ are $$C_1, C_2, \cdots, C_k$$. If one of them is not bipartite, then there is no repulsive-2-coloring for that component and hence no repulsive-2-coloring for $$G'$$. If all of them are bipartite, then there are two repulsive-2-colorings for each of them and hence $$2^k$$ repulsive-2-colorings of $$G'$$.