# 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:

1. G will already have some nodes colored Black.
2. 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<=32
Edges<=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.
• Since the graph has $O(1)$ vertices, there are only $O(1)$ possible colorings (think of each coloring as a boolean vector where each entry corresponds to a vertex). Each coloring can be tested in time proportional to the number of edges of the graph to determine if it satisfies your conditions. The number of edges is again in $O(1)$. The overall time required is therefore constant. – Steven Jul 12 '20 at 16:41