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.