# Even bi-coloring of regular graphs

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?

• Could I ask what motivated this question? It does seem interesting - even to classify the quartic graphs that admit a non-trivial (not all vertices white) such coloring would possibly be interesting. I took a look at the quartic graphs on between 5 and 7 vertices, and $K_5$, and $\overline{C_3 \cup C_4}$ admit non-trivial such colorings, but the octahedron and $\overline{C_7}$ do not. Commented Apr 30, 2014 at 22:31
• @Johannes If I understand you correctly, you want 4-regular graphs such that they allow the described coloring? If so, then you can use the program geng (within Sagemath) for the first part and check(for small values) all possible 2-colorings of such graphs. Commented May 1, 2014 at 10:15
• @PerryIverson - The problem is motivated by the statistical physics of black holes. Black holes feature holographic degrees of freedom: the number of black hole configurations scales with the exponent of the surface areas (and not with the exponent of a volumetric measure). Considering black holes as closed causal structures with local causal constraints, the question pops up: what is the simplest enumeration problem in which holographic scaling emerges? Regular graphs with the vertices colored according to local coloring rules provide us with an obvious discrete candidate. Commented May 1, 2014 at 17:04

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.

• This seems useful. Can this program be tuned to generate non-trivial (not 'all white') colorings only? Can you generate examples of order 8 and higher? (The largest non-all-white graph I have found so far is the Paley graph of order 9.) Commented May 1, 2014 at 18:17
• @Johannes Sure - one just needs to skip the subset containing all vertices in the function isGood. Doing this one finds out that apparently there are 11 such graphs of order 9, 42 on 10 vertices and 161 on 11 vertices. Commented May 1, 2014 at 20:28
• I agree with those figures; restricting them to connected graphs there are 41 of the 59 of order 10, 160 of the 265 of order 11 and 904 of the 1544 of order 12.
– jp26
Commented May 1, 2014 at 23:28
• @jp26,@Johannes Given this it makes more sense to classify graphs that do not admit a non-trivial coloring Commented May 2, 2014 at 11:40
• So it seems we have 1 valid graph of order 5, none of order 6, 1 of order 7, 1 of order 8, 11 of order 9, and 41 of order 10. Would you mind posting these 55 graphs (extending the list at the bottom of the answer; colorings don't need to be included as these are actually easy to find once valid graphs are identified). A study of these graphs will hopefully reveal some insights. Commented May 2, 2014 at 14:25

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.

• Given two valid colorings and mapping black to $1$, and white to $0$, the $mod_2$ (XOR) addition of the two colorings generates another valid coloring. However, many of the colorings thus generated will be identical due to graph symmetries. An example being the colorings of $K_5$: ignoring symmetries one would expect 1 coloring of all $0$'s, 5 colorings of one $0$ and four $1$'s, and 10 colorings of three $0$'s and two $1$'s. However, the symmetries of this complete graph reduce these 16 colorings to three distinct colorings distinguished by the number of $1$'s. Commented May 2, 2014 at 16:33
• Sure, but most graphs don't have any symmetries so I'm not sure identifying colorings modulo the action of the symmetry group is really the right way to think about it in this context. In any case, the existence of a nontrivial coloring is still detected by this determinant.
– Nate
Commented May 2, 2014 at 18:11

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.

• For #1, do you mean that if there are exactly 2 black vertices in the 4-regular graph, then you have the $K_5 - K_3$ structure? Also the graph $G$ for #1 is a 4-regular graph with all vertices colored white? Construction #2 is nice - I hadn't thought of that. Commented May 1, 2014 at 15:47
• Yes, I meant exactly 2, or, generalising; all pairs of black vertices at a distance of at least 3 means that each pair of black vertices have this neighbourhood.
– jp26
Commented May 1, 2014 at 17:35
• @jp26 - not sure if I understand construction no. 1. This construction adds 3 vertices to a valid graph with at least two black vertices, right? Can you show how to use this construction to go from $K_5$ to a valid order 8 graph? Commented May 1, 2014 at 18:35
• I was originally imagining it starting with a graph with all white vertices, but it will still work so long as vertices 1, 2, 3 and 4 are white. I'll add a picture of the 8 vertex graph.
– jp26
Commented May 1, 2014 at 19:41
• I now understand. Neat construction! It seems your construction can be modified into the addition of two black vertices: any closed loop through three white vertices can be replaced by seven edges connecting two additional black vertices to each of the three white vertices (six edges) and to each other (one edge). This generates the order 7 configuration out of an 'all white $K_5$'. Together with your +3 vertex addition construction, starting from $K_5$ this could potentially generate all valid graphs. Commented May 2, 2014 at 14:46