Even bi-coloring of regular graphs

Question

I am interested in exhaustively rendering quartic (4-regular) simple graphs of increasing order and bi-colored black and white such that the closed neighborhood of each vertex contains an even number of black vertices. Here, the closed neighborhood of a vertex is defined as the vertex itself plus its adjacent vertices.

A non-trivial (not 'all white') example is provided by the quartic graph of order five ($K_5$, the complete graph with 5 vertices) with two or four vertices colored black and the remaining ones colored white.

How to generate non-trivial graphs of higher order? Can this be done exhaustively?

Answer 1

You can use the following Sage program to gain some intuition into your problem. The function checkGraphs(n) iterates over all 4-regular graphs of order $n$ and writes out the respective graphs and the first legal coloring it finds.

def hasProperty(G,c):
    for v in G:
        if (c[v]+sum(c[u] for u in G[v])) % 2 == 1:
            return false
    return True

def isGood(G):
   for s in subsets(G):
        c = {v:0 if v in s else 1 for v in G}
        if hasProperty(G, c): 
            return c 
    return false
def checkGraphs(n):
    for G in graphs.nauty_geng("-d4 -D4 " + str(n)):
        print isGood(G), G.edges(labels=false)

For example

sage: checkGraphs(7)
{0: 0, 1: 0, 2: 0, 3: 1, 4: 1, 5: 1, 6: 1} [(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 5), (4, 6)]
{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0} [(0, 2), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 5), (3, 6), (4, 6)]

**Edit Here is a plot of all such graphs and the respective colorings.

Answer 2

I have come up with some constructions for generating graphs with more vertices;

1) If there is a set of just 2 black vertices that satisfies the property in a graph then it is straightforward to prove that they must come from a subgraph isomorphic to $K_2 + 3K_1$ (previously referred to as a $K_5 - K_3$). Using this we can add 3 vertices to any graph $G$ and have the property as follows:

Take any path on 4 white vertices $v_1$, $v_2$, $v_3$ and $v_4$ in $G$, remove the edges of the path and add new vertices and edges in as shown. All the new vertices will have two black (green) vertices in their neighbourhoods as will $v_2$ and $v_3$, all others will have their original numbers.

For $K_5$, let us choose its all white colouring and the path 5-2-3-6 with 5th vertex 4. We remove the edges 5-2, 2-3 and 3-6 and add vertices 1, 7 and 8. We add edges from 1, 2 and 3 to 7 and 8 and also an edge from 7 to 8 and edges from 1 to the start and end of the original path, 5 and 6. This gives the only graph with 8 vertices with your property.

The same reasoning also works if we start with a triangle of white vertices and add two vertices; for instance, with $K_6 - 3K_2$ we choose triangle 1, 2 and 3, remove the three edges of it and add in two vertices (7 and 8) adjacent to each other and 1, 2 and 3.

2) Take any 3-regular graph with $2n$ vertices and colour each vertex black; it will necessarily satisfy the property of having an even number of black vertices in the closed neighbourhood of each of its vertices. Now take any 4-regular graph to be the white vertices and subdivide $n$ edges and add new edges from these new valency 2 vertices to some black vertices.

Considering the general case:

Theorem: The subgraph $B$ induced by the black vertices must contain only vertices of odd valency.

Proof: Consider any vertex $v$ in $B$; we need $|N[v]|$ to be even to satisfy the property, so $|N(v)|$ must be odd, but that is the valency of $v$.

Corollary: There must always be an even number of vertices in $B$.

For the general case of generating all graphs with the property with $n$ vertices we can do one of the following based on the above ideas:

a) Construct all 3-regular graphs of order $b \leq \lfloor \frac{4n}{5} \rfloor$ and then consider ways to add $b$ edges to the remaining $n-b$ vertices to preserve 4-regularity and make sure each white vertex is joined to either 0, 2 or 4 black vertices. Now constructing all graphs with all vertices of valency 3 apart from one of valency 1 add white vertices again. Keep repeating this process until we get to the case of the black vertices forming a 1-regular graph in which case we know that the neighbourhoods of each of these edges is a $K_2 + 3K_1$.

However, this will necessarily bring quite a lot of duplication of effort as most graphs have black subgraphs of various orders, and there are also many different ways to join the white and black vertices together and some of these will lead to isomorphic graphs too.

b) Alternatively, we can use a recursive process to generate 4-regular graphs of order $n$ from those of slightly smaller orders (mostly $n-1$):

In the literature there are some results published such as "Construction of quartic graphs", S Toida (Journal of Combinatorial Theory, Series B Volume 16, Issue 2, April 1974, Pages 124–133) and more generally (with helpful references for small valency) "Generating r-regular graphs"; Guoli Ding, Peter Chen (Discrete Applied Mathematics Volume 129, Issues 2–3, 1 August 2003, Pages 329–343).

My preference would be to to use the operation which, given a 4-regular graph $G$, chooses two edges without any vertices in common in $G$, deletes the two edges and adds a new vertex $u$ adjacent to the four vertices of the deleted edges. Note that if all 4 vertices are white in a colouring $G$ then the new graph will also have your property with $u$ also coloured white.

The only circumstances under which a graph cannot be formed by this operation is that in which all vertices have many edges in the subgraph induced by the neighbourhood of each vertex. This means that we will either have $K_2 + 3K_1$ subgraphs (which guarantees the property) or $K_4$s. With a $K_4$ it is usually possible to shrink it down to a single vertex $v$ and then, if the resulting graph has the property and $v$ is white, we can guarantee that the original graph has the property too.

There are still some small problems to work through to get a complete classification, but hopefully this gives you some new ways to generate these graphs.

Answer 3

Not really a solution, but I think an important insight.

If we view 2-colorings as a maps from the vertex set to $\mathbb{Z}/2\mathbb{Z}$ sending black vertices to 1 and white vertices to 0, then the space of all 2 colorings on a fixed graph forms a vector space by pointwise addition. The condition that a neighborhood has an even number of black vertices translates to a homogeneous linear equation, so in particular the space of good colorings is a vector subspace. Hence there will always be a power of 2 number of such good colorings.

Let $A$ be the adjacency matrix of the graph, then these linear equations are just of the form $(A+I)x=0$ where I is the identity matrix and $x$ is a vector indicating which vertices we give which color. So the graph has a nontrivial good coloring iff the matrix $A + I$ doesn't have full rank over $\mathbb{Z}/2\mathbb{Z}$ which just means that $A+I$ has even determinant. As far as describing such graphs goes, I'm at a loss.