motivated from a physical context, we are currently interested in the following graph coloring problem:
Given a connected graph $G_n$ with $n$ vertices, how many colorings exist such that all white vertices have an odd number of black neighbors? We call this number $\omega(G_n)$.
(To the best of our knowledge, this particular coloring problem has not yet been studied, but if you have seen something like this, please let us know!)
As an example, consider the cycle graph with four vertices. There exist five such colorings:
In constrast, the fully connected graph of four vertices has nine such colorings:
Indeed, using completely different tools from physics, one can show that $\omega(G_n)$ is maximized by the fully connected graph, yielding the upper bound $\omega(G_n) \leq \begin{cases}2^{n-1} & n\text{ odd} \\ 2^{n-1}+1 & n\text{ even} \end{cases}$. Note that there is a total of $2^n$ colorings, thus, only about half of them can have the desired property.
Now we are interested in finding graphs that minimize $\omega(G_n)$ for a fixed number of vertices $n$. Exhaustively checking all connected graphs up to size 10 [Edit: this was a mistake, we only checked up to $n=8$. See Gordon's reply for a counter example with $n=9$ vertices] suggests that the graph minimizing $\omega(G_n)$ is given by the cycle graph of size $n$, but we have no clue on how to prove it.
Our questions are as follows: i) Is there an equivalent, similar or related graph coloring problem known in the literature? ii) Is there a graph theoretical argument that the cycle graph (among others) minimizes $\omega(G_n)$ for fixed $n$?
Lots of thanks in advance!