Graph that minimizes the number of b/w colorings where white vertices have an odd number of black

@Gordon Royle: Yes, it is correct that $\omega(K_{1,n})=\omega(K_{n+1})$.

More generally, $\omega$ is invariant under local complementation (inverting the neighborhood of a vertex).

Also note that both the cycle graph $C_n$ and the line graph $L_n$ fulfill the recursive formula $\omega(C_n)=\omega(C_{n-1})+\omega(C_{n-3})$ and $\omega(L_n)=\omega(L_{n-1})+\omega(L_{n-3})$. However, the initial values are different:

$\omega(C_3)=4$, $\ \ \omega(C_4)=5$, $\ \ \omega(C_5)=6$

$\omega(L_3)=4$, $\ \ \omega(L_4)=5$, $\ \ \omega(L_5)=8\ \ $ (and $\omega(L_1)=1$, $\ \ \omega(L_2)=3$)

This shows $\omega(C_n)<\omega(L_n)$ for all $n \ge 5$.

You can find the proof of the recursion formula in Sec. 6.2.3 of my Master's thesis. (Sorry about the copy-paste typo in Corollary 14; the subscript should read "line" and not "star".)

There is no graph-theoretical argument that the local equivalence class containing the cycle $C_n$ always minimises the value of $\omega$, because it is not true.

My smallest example is on 9 vertices with the following graph, which is just two pentagons merged at a single vertex.

This $9$-vertex graph has just 28 valid colourings, whereas $\omega(C_9) = 31$.

I verified this with some naive code in SageMath that simply tests each subset of the vertices of graph to see whether it can be the black vertices of a valid colouring - i.e., whether each vertex outside the subset is adjacent to an odd number of vertices in the subset.

def isValid(g,black):
    for v in g.vertices():
        if v not in black:
            val = len([w for w in g.neighbors(v) if w in black])
            if val % 2 == 0:
                return false
    return true    

def validSetList(g):
    return [s for s in Subsets(g.vertices()) if isValid(g,s)]

(I can't figure out how to enable syntax highlighting.)

Then the next couple of lines create the graph, call the function to return the list of valid sets, and determine how many there are:

h=Graph('HPXP?E@')
len(validSetList(h))

So I think the actual minimiser is going to be something like a bunch of 5-cycles merged at a single vertex, but I need to experiment some more.