Commensurability of 2-colorings of finite 4-valent graphs

Question

It is quite easy to show that given two finite 4-valent graphs $X,X'$ (I will take the convention that there is at most one edge between two vertices, but allow loops) there is a third such graph $X''$ which is a regular covering space of both; that is, $X$ and $X'$ are commensurable. (To see this it suffices to see that both graphs are quotients of the 4-valent tree by subgroups of finite index in $F_2$; equivalently one can build covering maps from $X$ and $X'$ to the 8 graph).

I am interested in a refinement of this statement (or its impossibility): given two colourings of the vertices of $X,X'$ as above by two colours (say red and black), is there a third finite 4-valent graph $X''$ with covering maps $\pi:X''\to X,\, \pi':X''\to X'$ and a red/black colouring such that (i)for any $x\in X$ (resp. $x'\in X'$) all vertices in the fiber $\pi^{-1}(x)$ (resp. $(\pi')^{-1}(x')$ are of the same colour and (ii) this coulour is the same as that of $x,x'$ in the original covering of $X,X'$? Of course one can rephrase this in terms of colourings on the 4-valent tree preserved by two free group actions.

I would be happy to know if such colourings exist (i.e. without specifying colouring on $X,X'$, is there a coloured $X''$ with $\pi,\pi'$ as above satisfying (i)?) and if there does, to learn about any quantitative results on the number of such colourings that might exist.

Answer 1

Here are two commensurability class invariants for these graphs that might help you with the refined statement you are looking for. The general answer to the question as stated is no, often $X''$ does not exist.

Assume $X$ and $X'$ are commensurable. $\pi: X'' \rightarrow X$ is degree $n$ and $\pi': X'' \rightarrow X'$ is degree $n'$.

Also, let's define the following: r (resp. r', r''), the number of red vertices in X (resp. X',X''), b (resp. b', b''), the number of black vertices in X (resp. X',X'').

Then $r'' = n\cdot r$, $b'' = n\cdot b$, $r'' = n'\cdot r'$, $b'' = n'\cdot b'$, so $r/b=r'/b'=r''/b''$, and so the ratio of red/black vertices is a commensurability class invariant.

However, consider the graphs as directed graphs with two edges coming into every vertex and two edges coming out. Although there is some freedom in this assignment, let's address that later. Given an edge labelling by directions, we can also define (RR,RB,BR,BB) by the counts of the directed edges that connect red vertices to red vertices, red vertices to black vertices, black to red and black to black respectively.

This is a vector in $\mathbb{Q}^4$ and by a similar argument to that above a necessary condition for $X$ and $X'$ to be commensurable is that for some pair of labelings of the edges of $X$ and $X'$, the vectors (RR,RB,BR,BB) and (RR',RB',BR',BB') corresponding to each labeling must be related by rational scalar multiple. Although this might be computationally expensive to determine, we of course have the weaker invariant that (RR,BB) and (RR',BB') must be related by a rational multiple.