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

Question

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?

Answer 1

Call a coloring where two nodes of same color must be linked by an edge (a.k.a. adjacent) attractive-coloring. The more common node coloring, where no two adjacent nodes are of the same color will be called repulsive-coloring.

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.

A graph can have a repulsive-2-coloring if and only if it is a bipartite graph. A connected bipartite graph has exactly two repulsive-2-coloring, i.e., assuming the two colors are red and black, we can color all nodes in one group red and all nodes in the other group black or the other way around.

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

Exercise (the well-known theorem on 2-colorable graphs). The (repulsively-)2-colorable graphs are exactly the bipartite graphs.