Number of ways to bicolor a graph with some constriants Given a graph G, I need to find the number of ways to color it using two colors Black and White.
Constraints:


G will already have some nodes colored Black.
Every node of color White needs to have one or more Neighbors of color Black.


The nodes that are colored Black will always be leaf nodes.
Vertices&lt;=32
Edges&lt;=Vertices^2
If you only care about graphs with at most $32$ vertices then just list all possible colorings. They are only a constant number ($2^{32}$). For each of them you can decide in constant time whether it is valid according to your constraints.
If you care about graphs with any number of vertices, then the problem is a generalization of the problem of counting the number of dominating sets in a graph, which is #P-complete even for special classes of graphs.