The de Bruijn graph $B_n$ of dimension $n$ (on the two-letter alphabet) is defined as the directed graph on $2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in 2^{n+1}$ we put an edge from the vertex $w_0 \dots w_{n-1}$ to the vertex $w_1 \dots w_n$. For the purposes of our problem, the edges are also $2$-colored, where the color of the edge determined by $w \in 2^{n+1}$ is $w_0$.

Given a finite directed graph $G$ with a $2$-coloring on the edges, we ask whether or not $G$ is the homomorphic image of $B_n$ for some $n$.

Is this problem decidable? That is, is there an algorithm which, given such a $G$, answers "yes" if and only if there exist $n$ and a homomorphism $B_n \to G$, and "no" otherwise?

Here, a homomorphism is required to preserve the $2$-coloring on edges. Formally, a homomorphism from $B_n$ to $G$ is a function $f \colon 2^n \to V(G)$ such that for every edge $(u,v)$ of color $b$, $(f(u), f(v))$ is an edge in $G$ of color $b$.

(We came upon this problem via an open problem in logic, see also our recent abstract.)